2

A sequence $a_n$ is defined by:

$a_1=1, a_2 = 1, a_n = a_{n-1} +2*a_{n-2}$ for all n> 2. show that $a_n = 1/3*(-1)^{n-3}+{2^n}/3$ by induction.

I'm not quite sure on how to approach this induction as I haven't really learnt it yet, but I think you prove its true for n=3 and then work out $a_n$ for n=n+1 but when I've tried i cant find the proof in it.

Smithy
  • 51
  • 1
    Why do you want to solve an exercise on induction if you have not yet learned induction? – 5xum Sep 11 '15 at 09:42
  • Because my assignment is due on monday and my tutorial time is also on monday so I only have 1 hour after my tutorial before its due so i want to get it done prior – Smithy Sep 11 '15 at 09:44
  • 1
    I see. In that case, the hints given below should be sufficient, and if anything else is unclear, you should check your lecture notes. You can also ask here, of course. – 5xum Sep 11 '15 at 10:15

3 Answers3

2

A not-so-inductive solution, for fun:

$$a_n=a_{n-1}+2a_{n-2}$$ can be rewritten $$a_n+a_{n-1}=2(a_{n-1}+a_{n-2}),$$ which is of the form $$b_n=2b_{n-1}.$$

We recognize a geometric progression of common ratio $2$, and with $b_2=2$,

$$b_n=2^{n-1}.$$

Now let us solve $$a_n+a_{n-1}=2^{n-1},$$ or, introducing $c_n=(-1)^{n-1}a_n$,

$$(-1)^{n-1}c_n=-(-1)^{n-2}c_{n-1}+2^{n-1},$$

$$c_n=c_{n-1}+(-2)^{n-1}.$$ We recognize the summation of a geometric progression of common ratio $-2$ and with $c_1=1$ get

$$c_n=\frac{(-2)^n-1}{-2-1},$$ $$a_n=\frac{2^n-(-1)^n}3.$$

  • Technically you cannot say "non-induction", since it is necessary for any proof, and indeed the reason your proof seems not to have it is because you used the mathematically non-rigorous "$\cdots$". Once you formalize that the induction will appear. And the geometric series formula requires at least one induction too. – user21820 Oct 01 '15 at 09:07
  • @user21820: rephrased. –  Oct 01 '15 at 09:52
  • Great! I like this kind of solution anyway, because it (partly) reveals the algebraic structure of recurrence relations. – user21820 Oct 01 '15 at 09:54
  • @user21820: actually this result is drawn from the factorization of the characteristic polynomial $x^2-x-2=(x-2)(x+1)$, which is used to solve the easy first-order recurrences $y_n-2y_{n-1}=0$, then $x_n+x_{n-1}=y_n$. –  Oct 01 '15 at 10:00
  • I know that very well, that's why I like it. Did you know that there is one trick for any separable quadratic higher-order functional equations that does not always extend to higher degree? Namely you repeat what you did with the other root, and then you just subtract one from the other to eliminate the non-constant part. – user21820 Oct 01 '15 at 10:04
  • @user21820: interesting. –  Oct 01 '15 at 10:12
1

First, show that this is true for $k=3$:

$a_{3}=a_{2}+2a_{1}=1+2=3=\dfrac{1+8}{3}=\dfrac{(-1)^{3-3}+2^{3}}{3}$

Second, assume that this is true for all ${k}\leq{n}$:

$a_{k}=\dfrac{(-1)^{k-3}+2^{k}}{3}$

Third, prove that this is true for $n+1$:

$a_{n+1}=$

$\color\red{a_{n}}+2\color\green{a_{n-1}}=$

$\color\red{\dfrac{(-1)^{n-3}+2^{n}}{3}}+2\left(\color\green{\dfrac{(-1)^{n-4}+2^{n-1}}{3}}\right)=$

$\dfrac{(-1)^{n-3}+2^n+2(-1)^{n-4}+2^n}{3}=$

$\dfrac{(-1)^{n-3}+2(-1)^{n-4}+2^n+2^n}{3}=$

$\dfrac{(-1)^{n-4}(-1+2)+2^{n+1}}{3}=$

$\dfrac{(-1)^{n-4}+2^{n+1}}{3}=$

$\dfrac{(-1)^{n-2}+2^{n+1}}{3}$

Please note that the assumption is used only in the part marked red and green.

barak manos
  • 43,109
0

First off, you prove that the statement is true for $n=3$. I assume that is simple enough.

Then, you assume that the fact is true for $n$, and you prove that it is then true for $n+1$. Alternatively, and this is much better here, you can assume that it is true for all $k$ such that $k\leq n$, then it is true for $n+1$.

So, your assumptions are now:

  • As before, you know that for all $k$, you have $a_k = a_{k-1} + 2a_{k-2}$
  • You now also know that for all $k\leq n$, you have $a_k = \frac13 (-1)^{k-3} + \frac{2^k}3$.

Now, I advise you to first look at the fact that

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

Now, replace the value of $a_n$ with $\frac13 (-1)^{n-3} + \frac{2^n}3$ and replace $a_{n-1}$ with $\frac13 (-1)^{(n-1)-3} + \frac{2^{(n-1)}}{3}$

You will get some expression $a_{n+1} = f(n)$, and if you can prove that this expression is equal to $$a_{n+1} = \frac13(-1)^{(n+1)-3} + \frac{2^{n+1}}3$$ you are done.

5xum
  • 123,496
  • 6
  • 128
  • 204