Intereting Posts

Prove that $2xy\mid x^2+y^2-x$ implies $x$ is a perfect square.
How to prove reflexivity, symmetry and transitivity for the following relation?
Minimum value of $\cos x+\cos y+\cos(x-y)$
How was this approximation of $\pi$ involving $\sqrt{5}$ arrived at?
Prove that if $a\equiv b \pmod m $ , then $a \bmod m = b \bmod m$
Angle brackets for tuples
Riemann Zeta Function and Analytic Continuation
Computing $\text{Gal}(\mathbb{Q}^{ab}/\mathbb{Q})$
Infinite Series $\sum\limits_{n=1}^\infty\frac{x^{3n}}{(3n-1)!}$
A curious identity on sums of secants
Sum of nil right ideals
The exceptional Klein four group
Proving $\lfloor 2x \rfloor = \lfloor x \rfloor + \lfloor x+0.5\rfloor$
Show that $\gcd(a,bc)=1$ if and only if $\gcd(a,b)=1$ and $\gcd(a,c)=1$
At most finitely many (Hamel) coordinate functionals are continuous – different proof

I’ve been trying to solve this recurrence relation for a week, but I haven’t come up with a solution.

$f(n)=5f(n/2)-6f(n/4) + n$

Solve this recurrence relation for $f(1)=2$ and $f(2)=1$

- Why do we need min to choose $\delta$?
- If $f:\to \mathbb{R}$ is continuous and nonnegative and $\int_a^b{f}=0$, then $f(x)=0$ for all $x\in $
- Continuous at exactly two points and differentiable at exactly one of them
- Must the (continuous) image of a null set be null?
- Where's the error in this $2=1$ fake proof?
- Prove that if a sequence $\{a_{n}\}$ converges then $\{\sqrt a_{n}\}$ converges to the square root of the limit.

At first seen it looks like a divide and conquer equation, but the $6f(n/4)$ confuses me.

Please help me to find a solution.

Kind regards,

- Solving a challenging differential equation
- How to prove reflexivity, symmetry and transitivity for the following relation?
- Forcing series convergence
- When adding zero really counts …
- Big Rudin 1.40: Open Set is a countable union of closed disks?
- DE solution's uniqueness and convexity
- Catalan Numbers Staircase bijection
- Show that $\arctan(n)$ is irrational for all $n \in \mathbb{N}$
- a generalization of normal distribution to the complex case: complex integral over the real line
- Why do we need min to choose $\delta$?

You can only define $f(2^k)$. (Try to define $f(3)$. It is impossible.) Hence make the transformation

$$

n=2^k, \quad \text{and define}\quad g(k)=f(2^k).

$$

Then for $g$ you have that

$$

g(0)=2, \quad g(1)=1\quad \text{and}\quad g(k+2)=5g(k+1)-6g(k)+2^{k+2}.

$$

If $2^{k+2}$ was not there, then $g$ would have to be of the form $g(k)=c_12^k+c_23^k$. With this additional term the general solution of the recursive relation is of the form $g(k)=c_12^k+c_23^k+c_3k2^k$. Just find the values of the constants.

Suppose we start by solving the following recurrence:

$$T(n) = 5 T(\lfloor n/2 \rfloor) – 6 T(\lfloor n/4 \rfloor) + n$$

where $T(0) = 0.$

Now let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$

be the binary representation of $n.$

We unroll the recursion to obtain an **exact** formula for all $n:$

$$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor}

[z^j] \frac{1}{1-\frac{5}{2}z+\frac{6}{4} z^2}

\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$

Observe that the roots of $$1-\frac{5}{2}z+\frac{6}{4} z^2

\quad\text{are}\quad\rho_0=1\quad\text{and}\quad\rho_1=\frac{2}{3}.$$

It follows that the coefficients of the rational term have the form

$$c_0 + c_1 \left(\frac{3}{2}\right)^j.$$

Actually solving for $c_{0,1}$ we obtain the formula

$$[z^j] \frac{1}{1-\frac{5}{2}z+\frac{6}{4} z^2}

= 3 \left(\frac{3}{2}\right)^j – 2.$$

This gives the **exact** formula for $T(n):$

$$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor}

\left(3 \left(\frac{3}{2}\right)^j – 2\right)

\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k$$

Now for an upper bound on this consider a string of one digits, which gives

$$T(n)\le

\sum_{j=0}^{\lfloor \log_2 n \rfloor}

\left(3 \left(\frac{3}{2}\right)^j – 2\right)

\sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k

= \frac{27}{2} \times 3^{\lfloor \log_2 n \rfloor}

– (12+4\lfloor \log_2 n \rfloor) 2^{\lfloor \log_2 n \rfloor} -\frac{1}{2}.$$

For a lower bound consider a one followed by a string of zeros, which gives

$$T(n)\ge

\sum_{j=0}^{\lfloor \log_2 n \rfloor}

\left(3 \left(\frac{3}{2}\right)^j – 2\right) 2^{\lfloor \log_2 n \rfloor}

= 9 \times 3^{\lfloor \log_2 n \rfloor}

– (8+2\lfloor \log_2 n \rfloor) 2^{\lfloor \log_2 n \rfloor}.$$

Joining the two bounds it follows that $T(n)$ is asymptotic as follows:

$$T(n)\in\Theta\left(3^{\lfloor \log_2 n \rfloor}\right)

= \Theta(2^{\log_2 n \times \log_2 3}) = \Theta(n^{\log_2 3})$$

with the leading coefficient between $9/2$ and $9.$

Now we are supposed to have $f(0)=0$, $f(1)=2$, and $f(2)=1,$ so start with

$$T(n) + \left(3 \left(\frac{3}{2}\right)^{\lfloor \log_2 n \rfloor} – 2\right)

2^{\lfloor \log_2 n \rfloor}.$$

This is equal to two at $n=1$ but equal to twelve at $n=2$, so we need an additional contribution of

$$T(n) + \left(3 \left(\frac{3}{2}\right)^{\lfloor \log_2 n \rfloor} – 2\right)

2^{\lfloor \log_2 n \rfloor}

– 11 (1-d_{\lfloor \log_2 n \rfloor-1})\times

\left(3 \left(\frac{3}{2}\right)^{\lfloor \log_2 n \rfloor-1} – 2\right)

2^{\lfloor \log_2 n \rfloor-1}.$$

This simplifies to (for $n\ge 2$)

$$ T(n) + 3^{\lfloor \log_2 n \rfloor+1} -2^{\lfloor \log_2 n \rfloor+1}

– 11 (1-d_{\lfloor \log_2 n \rfloor-1})\times

\left(3^{\lfloor \log_2 n \rfloor} -2^{\lfloor \log_2 n \rfloor}\right).$$

The behavior here is highly erratic but the formula is exact and the order of growth remains the same. Here is another Master Theorem computation at MSE.

- Basis of cotangent space
- How to learn commutative algebra?
- Centre of symmetric group algebra
- Is there a non-trivial countably transitive linear order?
- Simultaneous diagonlisation of two quadratic forms, one of which is positive definite
- How to resolve this absolute value inequality $|1+x^2|>|x|$?
- Counterexample for the stability of orthogonal projections
- Continuous function from the closed unit disk to itself being identity on the boundary must be surjective?
- The coupon collectors problem
- Prove that $2xy\mid x^2+y^2-x$ implies $x$ is a perfect square.
- Importance of construction of polygons
- Prove that $\lim_{x\to 2}x^2=4$ using $\epsilon-\delta$ definition.
- If $\frac{\sin^4 x}{a}+\frac{\cos^4 x}{b}=\frac{1}{a+b}$, then show that $\frac{\sin^6 x}{a^2}+\frac{\cos^6 x}{b^2}=\frac{1}{(a+b)^2}$
- How to prove $\int_0^1\tan^{-1}\left\frac{dx}{x}=\frac{\pi}{8}\ln\frac{\pi^2}{8}?$
- How to deal with this double summation?