Solving Recurrence Relation of $T(n)=4T(n-2)+2$

Question

Question

Solve Recurrence Relation of $T(n)=4T(n-2)+2$

Base case-: $T(1)=1,T(2)=2$

My Approach/solution

$$T(n)=4T(n-2)+2$$ $$T(n-2)=4T(n-4)+2 \tag{1}$$ $$T(n-4)=4T(n-6)+2 \tag{2}$$

Using $(1)$ and $(2)$ in my equation $$\begin{align*} T(n)&=4\cdot (4T(n-4)+2)+2\\ &=4^{2}\cdot T(n-2\cdot 2)+2\cdot 4^{1}+2\cdot 4^{0}\\ &=4^{2}\cdot(4T(n-6)+2)+2\cdot 4^{1}+2\cdot 4^{0}\\ &=4^{3}\cdot T(n-2\cdot 3)+2\cdot 4^{2}+2\cdot 4^{1}+2\cdot 4^{0}\\ \vdots \\ &=4^{k}\cdot T(n-2\cdot k)+2\cdot 4^{k-1}+...+2\cdot 4^{2}+2\cdot 4^{1}+2\cdot 4^{0} \end{align*}$$

Substituing $T(n-2\cdot k)$ by $2$, i.e $T(2)=2$ $$n-2\cdot k=2 \Rightarrow k=\frac{n-2}{2}$$

So our equation will look like

$$\begin{align*} T(n)&=2\cdot 4^{k}+2\cdot 4^{k-1}+...+2\cdot 4^{2}+2\cdot 4^{1}+2\cdot 4^{0}\\ T(n)&=2\cdot \left(4^{0}+4^{1}+4^{2}+...+4^{k-1}+4^{k}\right)\\ T(n)&=2\cdot \left(4^{0}\cdot \frac{(4^{k+1}-1)}{4-1}\right) \end{align*}$$

$k=\frac{n-2}{2}$

$$\begin{align*} T(n)&=2\cdot \left(\frac{(4^{k+1}-1)}{4-1}\right)\\ T(n)&=2\cdot \frac{2^{n}-1}{3} \end{align*}$$

Is it correct? Also if it is correct, can anyone hint me another approach as it is bit lengthy.

Thanks!

Answer 1

Using generating functions technique we have $$f(x)=\sum\limits_{n=0}T(n)\cdot x^n=T_0+1\cdot x+2\cdot x^2+\sum\limits_{n=3}T(n)\cdot x^n=\\ T_0+1\cdot x+2\cdot x^2+\sum\limits_{n=3}\left(4T(n-2)+2\right)\cdot x^n=\\ T_0+4\sum\limits_{n=3}T(n-2)\cdot x^n + x + 2\cdot x^2 +\sum\limits_{n=3}2\cdot x^n=\\ T_0+4x^2\sum\limits_{n=3}T(n-2)\cdot x^{n-2}-2-x+\sum\limits_{n=0}2\cdot x^n=\\ T_0+4x^2\sum\limits_{n=1}T(n)\cdot x^{n}-2-x+\sum\limits_{n=0}2\cdot x^n=\\ T_0-4T_0x^2-2-x+4x^2\sum\limits_{n=0}T(n)\cdot x^{n} +\sum\limits_{n=0}2\cdot x^n=\\ T_0-4T_0x^2-2-x+4x^2f(x)+ \frac{2}{1-x}$$ or $$f(x)=T_0-\frac{2+x}{1-4x^2}+\frac{2}{(1-x)(1-4x^2)}=\\ T_0-\left( \frac{5}{4(1-2x)}+\frac{3}{4(1+2x)} \right)+\left(-\frac{2}{3(1-x)}+\frac{2}{1-2x}+\frac{2}{3(1+2x)} \right)=\\ T_0-\frac{2}{3(1-x)}+\frac{3}{4(1-2x)}-\frac{1}{12(1+2x)}=\\ T_0-\frac{2}{3}\sum\limits_{n=0}x^n+\frac{3}{4}\sum\limits_{n=0}(2x)^n-\frac{1}{12}\sum\limits_{n=0}(-2x)^n=\\ T_0+\frac{2}{3}\sum\limits_{n=0}\left(\frac{3}{4}\cdot 2^n -\frac{1}{12}\cdot (-2)^n-\frac{2}{3}\right)x^n$$ or $$T(n)=\frac{3}{4}\cdot 2^n -\frac{1}{12}\cdot (-2)^n-\frac{2}{3}, n\geq 1$$ or $$T(n)=\frac{1}{12}\left(9\cdot 2^n + (-1)^{n+1}\cdot 2^n-8\right)$$ as presented by Dr. Sonnhard Graubner, only with a complete proof this time. The result is easy to validate $T(1)=1, T(2)=2, T(3)=6$.

Some of the shortcuts are explained here.

More learning materials here.

Answer 2

i think the right solution is given by $$T(n)=\frac{1}{12} \left(9\ 2^n+(-1)^{n+1} 2^n-8\right)$$ at first solve the equation $$T(n)=4T(n-2)$$ with $$T(n)=q^n$$

Answer 3

Hint: This is a linear second order recurrence equation. You can solve it with methods similar to solution methods for differential equations. Note thate recurrence equations are sometimes called difference equations, because they are the discrete form of differential equations. Notice that the generating functions method (as provided in the other answers) is also nothing else than the power series method used for differential equations.

The general solution is given as a superposition of the solution of

$$T_h(n+2)=4T_h(n)$$

which is the homogeneous equation and the particular solution. The homogeneous solution can be obtained by an exponential ansatz $T_h(n)= A^n$. Note you will get two solutions for $A$. They should be $A_{1,2}=\pm 2$.

Then find the particular solution by using the method of undetermined coefficients. Ansatz is a constant $T_p(n)=c=\text{const.}$. You should obtain $T_p(n)=-2/3$.

The general solution is given by:

$$T(n)=c_1A_1^n+ c_2A_2^n+(-2/3).$$

Determine the “constants of integration” $c_{1,2}$ by using your “initial values” for $T(1)$ and $T(2)$.