0

I need to show that $a_n= 2^n + a_{n-2}$ for $n$ is greater than or equal to $2$. Prior to that we are told that recursively define $a_0 = 1,\, a_1 = 3, a_2 = 5,\, $ and $ a_n = 3a_{n-2} + 2a_{n-3}$ for $n$ is greater than or equal to $3$.

I tried writing out a characteristic equation and got the following: $x^3 - 3x - 2 = 0$, for which the solutions I got were $x = -1, 2$. I tried solving for constants, but I ended up getting $4\over3$ and $-1\over3$. If I could get some guidance as to how to approach the problem and whether I was on the right track, I would greatly appreciate it.

The third solution that I got seemed to be zero. I did the following math:

$a_0 = 1 = C_1 + C_3\\a_1 = 3 = -C_1 - C_2 + 2C_3\\a_2 = 5 = C_1 + 2C_2 + 4C_3$

Matt
  • 21
  • You should have gotten one more solution since that's a cubic. If there is a multiplicity then you need need to try $a_n = Ar^n + Bnr^n$. – Jared Apr 22 '16 at 03:20
  • @Jared I made an edit in the question to show the math I did. I wasn't sure what you meant when you said if there's a multiplicity. – Matt Apr 22 '16 at 03:32
  • By "a multiplicity" he means a root with multiplicity greater than one such as is the case with the characteristic polynomial $(x-2)^3=0$. Note: $x^3-3x-2 =(x-2)(x+1)^2$, so the root $-1$ has multiplicity two and should appear twice in the closed form solution. You should expect then that it will be of the form $a_n=c_1(-1)^n + c_2n(-1)^n + c_3(2)^n$ – JMoravitz Apr 22 '16 at 03:49
  • 1
    Your system of equations seems to suggest that you were already aware of this (though it wasn't well stated if that is the case), but would seem to contain an error in the second line, it should read instead $a_1=3=-c_1\color{red}{-}c_2 + 2c_3$ – JMoravitz Apr 22 '16 at 03:53
  • I did unfortunately type the second line in wrong in that I messed up with the second sign. I'm having issues moving on from this point. I tried doing some manipulations of the equations, but can't seem to find any solutions for any of the c values. – Matt Apr 22 '16 at 04:05

1 Answers1

1

HINT: I suggest a very different approach. You know that

$$a_n=3a_{n-2}+2a_{n-3}\;,$$

and you want to show that

$$a_n=2^n+a_{n-2}\;.\tag{0}$$

In order for this to be true, it must be the case that

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

and hence that $a_{n-2}+a_{n-3}=2^{n-1}$ for each $n\ge 3$ or, equivalently, that

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

for each $n\ge 1$. Conversely, if you knew that $(1)$ was true for all $n\ge 0$, you could easily combine it with the original recurrence to deduce $(0)$. Try to prove $(1)$ by induction on $n$. Your induction hypothesis should be that $(1)$ holds for $n=k$ and $n=k-1$, say, and you’ll use it and the original recurrence to prove that $(1)$ holds for $n=k+1$.

Brian M. Scott
  • 616,228
  • Thanks so much for the answer. As for the actual induction, with n = k +1, would I simply plug that into (1), and then show that it works for a value of k greater than or equal to 1? Or would I need to try to manipulate the left side of the equation such that I am able to get it to be equal to the right side? Thanks. – Matt Apr 22 '16 at 16:56
  • @Matt: The latter. Try to manipulate $a_{k+1}+a_k$ to get $2^{k+2}$; your first step should be to use the original recurrence to get rid of $a_{k+1}$. Then you’ll use both induction hypotheses, followed by a little algebra. – Brian M. Scott Apr 23 '16 at 01:48