0
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – logarithm May 12 at 12:06
  • $\begingroup$ 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! $\endgroup$ – Gerry Myerson May 12 at 12:52
  • $\begingroup$ Would you like to engage with the comments and answers that have been posted, 173379? $\endgroup$ – Gerry Myerson May 14 at 3:21
  • $\begingroup$ Are you still here, 173379? $\endgroup$ – Gerry Myerson May 15 at 5:53
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.