2

I need to solve the following recurrence relation:

$a_n=3a_{n-1}-2a_{n-2}+2^n$

For the homonogenous part, it's quite simple and I get:

$a_n^h=\lambda_1+\lambda_22^n$

The nonhomonogenous part is where I get lost. Since one of the solutions from the equation (that I got from Euler's substutution) turns out to be $2$, I need to use the following substitution for $a_n$ :

$a_n=A2^nn^m$

Which means I get:

$An^m2^n-3A(n-1)^m2^{n-1}+2A(n-2)^m2^{n-2}=2^n$

I can easily reduce this to:

$An^m-3A(n-1)^m2^{-1}+A(n-2)^m2^{-1}=1$

But I'm not sure how to continue here. I'd be grateful if anyone could help me point me to the right direction. I'm not sure how to factor $n^m$.

EDIT:

The solution (thank you for helping!):

$a_n=\lambda_1+\lambda_2*2^n+2*n*2^n$

user3104311
  • 99
  • 2
    "point me to the right direction" How to choose $m$ so as to make $$C=2n^m-3(n-1)^m+(n-2)^n$$ constant? Then set $A=2/C$ and you are done. – Did Aug 29 '18 at 14:52
  • That's it I assume, thank you! – user3104311 Aug 29 '18 at 14:54
  • Isn't setting $A=2/C$ unnecessary? If I can simply plug $m=0$ into the equation and just solve it that way. – user3104311 Aug 29 '18 at 14:57
  • 1
    No, $m=0$ leaves you with $$A-3A/2+A/2=1$$ which has no solution. So, I guess my first comment could read "How to choose $m$ so as to make $C=...$ constant and nonzero?" – Did Aug 29 '18 at 15:00
  • Just realized it would be the same as not even taking $x=2$ into consideration. Turned out correct for $m=3$. – user3104311 Aug 29 '18 at 15:10
  • No, $m=3$ does not work. – Did Aug 29 '18 at 15:11
  • Does this mean that I have to just keep plugging in different values until I find something or am I missing something really obvious? – user3104311 Aug 29 '18 at 15:13
  • You are missing something really obvious. Which values of $m$ did you try? – Did Aug 29 '18 at 15:15
  • $m=1$ seems to work. Not sure how I got the most obvious one wrong. Thank you. – user3104311 Aug 29 '18 at 15:22
  • You are welcome. Write down a solution to your own question? This is the way to really grasp the subject and is recommended on the site anyway, so... – Did Aug 29 '18 at 15:25

1 Answers1

3

Alternate solution as a reference. Since the non-homogeneous is kind of special, we can proceed as follows.

Solution. $\blacktriangleleft$ Divide the equation by $2^n$ we have $$ \frac {a_n}{2^n} = \frac 32 \cdot \frac {a_{n-1}} {2^{n-1}} - \frac 12 \cdot \frac {a_{n-2}} {2^{n-2}} + 1. $$ Let $b_n = a_n \cdot 2^{-n}$, then replace $n$ by $n+1$ we have two equations: \begin{alignat*}{5} &b_{n+1} & - \frac 32 &b_n& + &\frac 12 b_{n-1}& &&= &1&\\ & & &b_n& - & \frac 32 b_{n-1}& + &\frac 12 b_{n-2}& = &1& \end{alignat*} Subtract them we get a homogeneous recurrence $$ b_{n+1} - \frac 52 b_n + 2 b_{n-1} - \frac 12 b_{n-2} = 0, $$ whose characteristic polynomial is $$ 2x^3 - 5x^2 + 4 x -1 = (x-1)(2x^2-3x + 1) = (x-1)^2 (2x-1), $$ hence the general solution is $$ b_n = (c_1 + c_2 n) + c_3 2^{-n}, $$ and the solution to the original equation is $$ a_n = c_3 + (c_1 + c_2 n)\cdot 2^n. \blacktriangleright $$

Now that I think about it, this seems like an indirect application to the Euler substitution. Maybe my post is redundant here...

xbh
  • 8,835