Resolving $T(n) = 9T(n-2)+1$ and $T(n) = T(n-4)$ I'm tasked to give the best possible asymptotic bound for the following recurrences:

a) $T(n) = 9T(n-2)+1$ 

and 

b) $T(n) = T(n-4)$



For a) I used the iteration method:

$$ T(n) = 9 \cdot T(n-2)+1 = 9^k \cdot T(n-2k) + 9 \cdot (k-1) + 1 =... $$

By solving the equation $n-2k = 1$ we get:

$$ ... =  9^{\frac{n-1}{2}} + 9 \cdot \left(\frac{n-1}{2} - 1\right) + 1 \\
 = 3^{n-1} + 4.5n -9.5 $$

Therefore we get: $$ T(n) = \Theta(3^{n-1})$$



For b) I also used the iteration method:

$$T(n) = T(n-4) = ... = T(n-4k) =... $$

and by solving $ n - 4k = 1$ we get:

$$ ...= 1 $$

This proves that $$ T(n) = \Theta(1) $$



Is this correct? 

Thanks for any answers.
Try generating functions ...



a) First one 
$$f(x)=\sum\limits_{n=0}T(n)x^n=T(0)+T(1)x+\sum\limits_{n=2}\left(9T(n-2)+1\right)x^n=\\
T(0)+T(1)x+9x^2\sum\limits_{n=2}T(n-2)x^{n-2}+\sum\limits_{n=2}x^n=\\
T(0)-1+T(1)x-x+9x^2\sum\limits_{n=0}T(n)x^{n}+\sum\limits_{n=0}x^n=\\
T(0)-1+\left(T(1)-1\right)x+9x^2f(x)+\frac{1}{1-x}$$

Or
$$f(x)=\frac{T(0)-1}{1-9x^2}+\frac{\left(T(1)-1\right)x}{1-9x^2}+\frac{1}{(1-9x^2)(1-x)}=\\
\frac{T(0)-1}{2}\left(\frac{1}{1-3x}+\frac{1}{1+3x}\right)+\frac{T(1)-1}{6}\left(\frac{1}{1-3x}-\frac{1}{1+3x}\right)-\frac{1}{8(1-x)}+\frac{3}{4(1-3x)}+\frac{3}{8(1+3x)}=\\
\frac{1}{1-3x}\frac{6T(0)+2T(1)+1}{12}+\frac{1}{1+3x}\frac{12T(0)-4T(1)+1}{24}-\frac{1}{8(1-x)}=\\
\frac{6T(0)+2T(1)+1}{12}\left(\sum\limits_{n=0}(3x)^n\right)+\frac{12T(0)-4T(1)+1}{24}\left(\sum\limits_{n=0}(-3x)^n\right)-\frac{1}{8}\left(\sum\limits_{n=0}x^n\right)=\\
\sum\limits_{n=0}\left(\frac{6T(0)+2T(1)+1}{12}\cdot 3^n+\frac{12T(0)-4T(1)+1}{24}\cdot (-3)^n-\frac{1}{8}\right)x^n$$
Or 
$$T(n)=\frac{6T(0)+2T(1)+1}{12}\cdot 3^n+\frac{12T(0)-4T(1)+1}{24}\cdot (-3)^n-\frac{1}{8}$$



b) Second one 
$$f(x)=\sum\limits_{n=0}T(n)x^n=T(0)+T(1)x+T(2)x^2+T(3)x^3+\sum\limits_{n=4}T(n)x^n=\\
T(0)+T(1)x+T(2)x^2+T(3)x^3+x^4\sum\limits_{n=4}T(n-4)x^{n-4}=\\
T(0)+T(1)x+T(2)x^2+T(3)x^3+x^4f(x)$$
Or
$$f(x)=\frac{T(0)+T(1)x+T(2)x^2+T(3)x^3}{1-x^4}=\frac{T(0)+T(1)x+T(2)x^2+T(3)x^3}{4}\left(\frac{1}{1-x}+\frac{1}{1-ix}+\frac{1}{1+ix}+\frac{1}{1+x}\right)$$
I leave the remaining part as an exercise ...
Applying a) twice, we can deduce that $$T(k+4) = 9T(k+2)+1 = 9(9T(k)+1)+1 = 81T(k)+10$$ for any $k$.  Applying b), we have $$T(k+4) = T(k).$$  Combine these two conclusions we have $$T(k) = \frac18,$$ for any $k$.