Please help me understand the method used for solving Linear homogeneous and non-homogeneous recursive functions?

Question

f(n)=2*f(n-1)+2^n

I just want to make it clear I can solve the question by following the rules, my doubts in using the usual method are

1. Why do we guess the solution $f(n)=k^{n}$ rather than some polynomial?
2. After finding the roots how do the linear combination of the solution of characteristic equation is equal to $f(n)$?
3. Similarly, what is the logic behind the guessing of the particular solution?

Answer 1

For your example $$f_n=2f_{n-1}+2^n$$ let $f_n=2^n g_n$ to end with $$g_n=2g_{n-1}+1$$

Answer 2

The example you gave is a type of linear non-homogeneous recurrence relation with constant coefficients usually written in the form $$ a_{n} - 2 \cdot a_{n-1} = 2^{n} \text{ for } n \geq 1, \tag{1} $$ with initial condition $a_{0} = C$. Solution is of the form $$ a_{n} = z_{n} + b_{n}, $$ where $z_{n}$ is the solution of the associated homogeneous recurrence relation in this case $$ a_{n} - 2 \cdot a_{n-1} = 0 $$ with associated characteristic equation in this case $x - 2 = 0$ and solution $z_{n} = C \cdot 2^{n}$. When function on the right hand side of Equation (1) is of the form $\alpha^{n}$ and when $\alpha$ is the root of the characteristic equation with multiplicity $s$, the guess for the particular solution is of the form $$ b_{n} = n^{s} \cdot \alpha^{n}. $$ In your example $b_{n} = n \cdot 2^{n}$ and final solution of (1) is $$ a_{n} = C \cdot 2^{n} + n \cdot 2^{n}. $$ To see why this works, you need to prove some propositions, for example the following. Proposition: Let $a_{n} = c_{1} a_{n-1} + ... + c_{k} a_{n-k} + f(n)$ be a linear non-homogeneous recurrence and assume the sequence $b_{n}$ satisfies the recurrence. Then another sequence $a_{n}$ satisfies the non-homogeneous recurrence if and only if $z_{n} = a_{n} - b_{n}$ is also a sequence that satisfies the associated homogeneous recurrence. You can find the proof here.

Another approach is to use generating functions. Let $$ G(x) = a_{0} + a_{1} x + ... + a_{n} x^{n} + ... = \sum_{n=0}^{\infty} a_{n} x^{n} $$ be the generating function for the sequence $a_{n}$. Then \begin{align*} G(x) &= C + \sum_{n = 1}^{\infty} (2\cdot a_{n-1} + 2^{n}) x^{n} \\ &= C + 2 \sum_{n=1}^{\infty} a_{n-1}x^{n} + \sum_{n=1}^{n}(2x)^{n} \\ &= C + 2 x (a_{0} + a_{1}x + a_{2}a^{2} + ...) + 2x(1 + (2x)^{1} + (2x)^{2} + (2x)^{3} + ...) \\ &= C + 2 x \cdot G(x) + 2x \cdot \frac{1}{1 - 2x} \end{align*} which we can solve for $G(x)$ \begin{align*} G(x) &- 2x\cdot G(x) = C + 2x \frac{1}{1 - 2x} \\ G(x) &= C \frac{1}{1-2x} + 2x \frac{1}{(1-2x)^{2}} \\ G(x) &= C (1 + (2x) + (2x)^{2} + ... + (2x)^{n} + ...) + \\ & + 2x (1 + 2(2x) + 3(2x)^{2} + ... + n(2x)^{n-1} + ...) \end{align*} and from this we see the coefficient of $x^{n}$ is $$ a_{n} = C \cdot 2^{n} + n \cdot 2^{n}. $$