<s>[INST] Solving recurrence with substitution I am trying to solve this recurrence $T(n) = 4T(n − 2) + 2^{2n}$ by using substitution and knowing $T(1)=1,T(2)=2$ and here is my attempt:Expanding $T(n)=4T(n-2)+2^{2n}$ using $T(n-2)=4T(n-4)+2^{2(n-2)}$, we get $T(n)=4(4T(n-4)+2^{2(n-2)})+2^{2n}=4^2T(n-4)+2^{2n-2}+2^{2n}=4^2(4T(n-6)+2^{2(n-4)})+2^{2n-2}+2^{2n}=4^3T(n-6)+2^{2n-4}+2^{2n-2}+2^{2n}=...=4^k(T(n-2k)+2^{2n-2k+2}+2^{2n-2k+4}+...+2^{2n}$.Substituting $T(n-2k)=2, i.e. T(2)=2$, $n-2k=2$ then $k=\frac{n-2}{2}$, so our equation looks like $2^{2k}+2^{2n-2k+2}+2^{2n-2k+4}+...+2^{2n}$ with $k=\frac{n-2}{2}$, $2^{2k}+2^{2n-2k+2}+2^{2n-2k+4}+...+2^{2n}=2^{n-2}+2^{n+4}+...+2^{2n}=2^{n-2}+\frac{2^{n+4}(1-2^{\frac{n-4}{2}})}{1-2}=2^{n-2}+2^{\frac{3n+4}{2}}-2^{n+4}$. However I think this answer doesn't satisfy $T(2)=2$ and I really don't know where went wrong. Is there another way to do this problem?
 [/INST] This is a linear difference equation. You can get the solution as follows:

*

*Compute the general solution of the homogenous equation $T_n = 4 T_{n-2}$, which is $H_n = c_1 \cdot 2^n +c_2 \cdot (-2)^n$.


*Obtain a particular solution of the complete equation by trying something similar to the RHS, i.e. $P_n = k \cdot 4^n$, and compute $k$ substituting in the equation. One possibility is $P_n = \frac{4}{3} \cdot 4^n$.


*The general solution to our equation is given by
$$
T_n = H_n + P_n = c_1 \cdot 2^n +c_2 \cdot (-2)^n + \frac{4}{3} \cdot 4^n
$$


*From the conditions on $T_1, T_2$, compute $c_1, c_2$ to get the final answer:
$$
T_n = -\frac 72 2^{n}-\frac 43 (-2)^{n} + \frac 43 \cdot 4^n
$$
</s>