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?
• If $S$ denotes the shift operator, this is $Sf(n)=f(n+1)$, and you write the homogneous equation as $P(S)f=0$ for some polynomial $P$ with constant coefficients, then you can factor the polynomial and get an equation like $\prod_{i=1}^n(S-r_i)f=0$. Now you can see that if $f$ satisfies at least one of the equations $(S-r_i)f=0$, then it also satisfies the previous one. The solution of $(S-r_i)f=0$ is the sequence $f(n)=Ar_i^{n}$. – logarithm May 12 at 12:06
• 1) The solution of $f(n)=rf(n-1)$ is obviously $f(n)=Ar^n$ for $A$ arbitrary – just think about it. 2) is a word salad – I can't parse what you have written. 3) When the inhomogeneous term is $c^n$, there's a particular solution of the form $Bc^n$ – except when that's also a solution of the homogeneous equation, as it is here. Then you have to multiply by an appropriate power of $n$. But there have been dozens of questions on this site about solving this kind of recurrence. Have a search! – Gerry Myerson May 12 at 12:52
• Would you like to engage with the comments and answers that have been posted, 173379? – Gerry Myerson May 14 at 3:21
• Are you still here, 173379? – Gerry Myerson May 15 at 5:53

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}.$$
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$$