How can I solve the recurrence relation:$F\left(n\right)=F\left(n-1\right)+2F\left(n-2\right),\:F\left(0\right)=1,F\left(1\right)=1$

Question

I've been trying to solve it using Power Series and Partial Fractions but got stuck with.

Answer 1

Let $F(n) = x^n$. Then we have $x^n - x^{n-1} - 2x^{n-2} = x^{n-2}(x^2 - x - 2) = 0$. So in order to have solution(s) in the form of $Cx^n$ we should set $$x^2 - x - 2 = (x-2)(x+1)= 0 \implies x = 2 , -1$$ Combining these solutions, the general solution is $F(n) = a_12^n + a_2(-1)^n$. Using initial conditions we have $$a_1 + a_2 = 1$$ And $$2a_1 -a_2 = 1$$ Which leads to $F(n) = \frac{2}{3}2^n+\frac{1}{3}(-1)^n$. We can check that easily using WA. It's really like solving the differential equation $y'' - y' - 2y = 0$.

Edit: Actually we can also use unilateral $\mathcal{Z}-$transform (which is similar to Laplace transform). It's defined by $$X(z) = \sum_{n = 0}^{\infty}x[n]z^{-n}$$We can prove that $\mathcal{Z}\{x[n-1]\} = z^{-1}X(z) + x[-1]$ which leads to $\mathcal{Z}\{x[n-2]\} = z^{-2}X(z) + z^{-1}x[-1] + x[-2]$. So we have $$X(z) - (z^{-1}X(z) + x[-1]) - 2(z^{-2}X(z) + z^{-1}x[-1] + x[-2]) = 0$$ It's easy to compute $x[-1]$ and $x[-2]$ by extrapolating $$x[1] = x[0] + 2x[-1] \implies x[-1] = 0$$ $$x[0] = x[-1] + 2x[-2] \implies x[-2] = \frac{1}{2}$$ The result is $$X(z) = \frac{1}{1 - z^{-1} - 2z^{-2}}$$ Apply partial fraction decomposition $$\frac{1}{1 - z^{-1} - 2z^{-2}} = \frac{-1}{(z^{-1} + 1)(2z^{-1} - 1)} = \frac{1}{3}(\frac{1}{z^{-1} + 1}) - \frac{2}{3}(\frac{1}{2z^{-1} -1}) = \frac{1}{3}(\frac{1}{1 -(-1)z^{-1}}) + \frac{2}{3}(\frac{1}{1- (2)z^{-1}})$$ Also $\mathcal{Z}\{a^n u[n]\} = \frac{1}{1-az^{-1}}$ when $|z| \gt |a|$. Applying inverse transform to both sides $$x[n] = \frac{1}{3}(-1)^n u[n] + \frac{2}{3}2^n u[n]$$ Which is the same answer as previous.