3
$\begingroup$

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!

$\endgroup$
8
  • $\begingroup$ Note that the $T(n)$ you have found applies only to $n$ even $\endgroup$
    – user418131
    Commented Oct 10, 2017 at 15:26
  • $\begingroup$ $$T(1)=2\cdot \frac{2-1}{3}=\frac{2}{3}\neq 1$$ $\endgroup$ Commented Oct 10, 2017 at 15:29
  • $\begingroup$ $T(n)=4T(n-2)+2$ has characteristic polynomial $x^2-4=0$ and constant nonhomogenous part. The characteristic polynomial factors as $(x+2)(x-2)=0$. This implies that the closed form solution will be of the form $T(n)=c_1\cdot 2^n+c_2\cdot (-2)^n+d$ where $c_1,c_2,d$ are constants that can be solved for given initial conditions. $\endgroup$
    – JMoravitz
    Commented Oct 10, 2017 at 15:30
  • $\begingroup$ i forgot to mention , it will work for $n=\text{even case}$ $\endgroup$
    – laura
    Commented Oct 10, 2017 at 15:30
  • 1
    $\begingroup$ @rtybase i will be glad to learn $\endgroup$
    – laura
    Commented Oct 10, 2017 at 18:56

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$$

$\endgroup$
2
  • $\begingroup$ sir is my solution wrong? $\endgroup$
    – laura
    Commented Oct 10, 2017 at 15:28
  • $\begingroup$ How did you find this solution? $\endgroup$
    – Arnaud D.
    Commented Oct 10, 2017 at 16:03
0
$\begingroup$

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)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .