0

In Proof by Induction - Sequence of integers the sequence of integers $a_1$, $a_2$, ... is defined as:

$$a_1 = 3$$ $$a_2 = 6$$ $$a_n = 5a_{n-1} - 6a_{n-2} + 2$$ for all $n\ge3$

And the question is posed of proving that $a_n = 1 + 2^{n-1} + 3^{n-1}$ for all $n\in\mathbb N$.

The base case and inductive hypothesis are clear to me, and in the inductive step I end up with:

$$a_{k+1} = 5a_k - 6a_{k-1} + 2$$

This, assuming the inductive hypothesis holds of $a_{k+1}$ and $a_{k}$, is equal to

$$5(1 + 2^{k-1} + 3^{k-1}) - 6(1 + 2^{k-2} + 3^{k-2}) + 2$$

From this, I arrive at $(5 + 25^{k -1}) - (6 + 20^{k -2}) + 2 = 5(1 + 5^{k -1}) - 2(3 + 10^{k -2}) + 2$, but I am unable to see how this is equivalent to $a_{k + 1} = 1 + 2^{k} + 3^{k}$.

Can anyone help me here?

Edward.Lin
  • 175
  • Have you broken open the parentheses? – ncmathsadist Jun 09 '21 at 20:54
  • Hint: $6=3\cdot2$ – Will Orrick Jun 09 '21 at 20:56
  • Yes, and I arrive at $(5 + 25^{k -1}) - (6 + 20^{k -2}) + 2 = 5(1 + 5^{k -1}) - 2(3 + 10^{k -2}) + 2$, but cannot get further. – Edward.Lin Jun 09 '21 at 20:58
  • Setting $k=2$ in your formula gives $(5+25)-(6+1)+2=5(1+5)-2(3+1)+2$, which reduces to $25=24$. Something must be wrong. I suspect the problem may be certain misconceptions about the manipulation of exponents, but it's hard to determine what those might be. – Will Orrick Jun 09 '21 at 21:15
  • 1
    Looking at your expression a bit more, it seems you are performing manipulations like $a^n+b^n=(a+b)^n$ and $c\cdot a^n=(ca)^n$. These are not correct, as testing a few numerical examples will show. A good start would be to find some review material about basic exponent manipulations and do some practice with that first. – Will Orrick Jun 09 '21 at 21:32
  • @Will Orrick Yes, I actually don't properly know the rules for manipulating these equations and have been looking for a resource which explains them to me. A friend just showed me the answer but I cannot follow the manipulations of the equations, which I dont think I learnt at school. Where can I read all of these rules? – Edward.Lin Jun 09 '21 at 21:35
  • Searching on "rules for powers" turns up a lot of good sites. Here's one: Math Insight – Will Orrick Jun 09 '21 at 21:40

0 Answers0