<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] Hint
$$T(n)=4T(n-2)+4^{n}$$
$$T(n)=4^2T(n-4)+4^{n}+4^{n-1}$$
by induction, find that
$$T(n)=4^kT(n-2k)+4^{n}+4^{n-1}+...+4^{n-(k-1)}.$$
Now, take $n=2k$ and $n=2k+1$ and find your general formula.
</s>