1
$\begingroup$

This is my problem:

The recurrence relation is \begin{aligned} a_{n} = 3a_{n-1}-2a_{n-2} \end{aligned} This is given that $a_{0}=0, a_{1}=2$.

From the above information I calculated

\begin{aligned} a_{2} &=3(a_{2 - 1}) - 2(a_{2 - 2}) = 3(a_{1}) - 2(a_{0}) = 3(2) - 2(0) = 6 \\ a_{3} &=3(a_{3 - 1}) - 2(a_{3 - 2}) = 3(a_{2}) - 2(a_{1}) = 3(6) - 2(2) = 14 \\ a_{4} &=3(a_{4 - 1}) - 2(a_{4 - 2}) = 3(a_{3}) - 2(a_{2}) = 3(14) - 2(6) = 30 \end{aligned}

I have been trying to solve this recurrence relation for quite some time and have come up with the solution

\begin{aligned} a_{n} = 2 * (2^{n} - 1) \end{aligned}

I am having trouble proving this solution by induction.

My Attempt:

Base Cases:

$$a_0 = 0 = 2(2^0-1)\\a_1 = 2 = 2(2^1-1)$$

Inductive Hypothesis: Assume that $a_k = 2(2^k-1)$ and $a_{k-1} = 2(2^{k-1}-1)$

Inductive Step: $$a_{k+1} = 3a_{(k+1)-1}-2a_{(k+1)-2} = 3a_{k}-2a_{k-1}$$

By the inductive hypothesis $a_k = 2(2^k-1)$ and $a_{k-1} = 2(2^{k-1}-1)$,

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

From here it is just simplifying but I cannot get it to simplify to the correct expression.

Any ideas?

$\endgroup$
2
  • $\begingroup$ Write $3=2+1$ and remember that $2^{n-1}-2^{n-2} = 2^{n-2}$. $\endgroup$
    – user208649
    Commented Sep 22, 2020 at 10:39
  • $\begingroup$ You're missing a ) $\endgroup$ Commented Sep 22, 2020 at 10:41

1 Answer 1

0
$\begingroup$

Assume it holds for $n=k$ (so it also holds for $n<k$), then for the induction step \begin{align} a_{k+1}&=3a_{k}-2a_{k-1}\\ &=3(2(2^{k}-1))-2(2(2^{k-1}-1))\\ &=3(2^{k+1}-2)-2(2^{k}-2)\\ &=3\cdot2^{k+1}-6-2^{k+1}+4\\ &=2\cdot2^{k+1}-2\\ &=2(2^{k+1}-1) \end{align}

as required.

$\endgroup$
7
  • $\begingroup$ I claim that this is by no means an inductive proof. Can you state clearly the induction hypothesis (i.e. some $P(k)$), and where $P(k)\implies P(k+1)$ ? $\endgroup$
    – user65203
    Commented Sep 24, 2020 at 12:39
  • $\begingroup$ $P(k),P(k-1)\implies P(k+1)$ from the second equality. $\endgroup$
    – Alessio K
    Commented Sep 24, 2020 at 12:42
  • $\begingroup$ What is $P(k)$ ? $\endgroup$
    – user65203
    Commented Sep 24, 2020 at 12:42
  • $\begingroup$ $P_{k}=a_{k}$. The OP did induction above. $\endgroup$
    – Alessio K
    Commented Sep 24, 2020 at 12:43
  • $\begingroup$ $a_k$ is not a predicate, it is an element of a sequence. You cannot "prove" $a_k$, and even less write $a_k\implies a_{k+1}$. $\endgroup$
    – user65203
    Commented Sep 24, 2020 at 12:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .