1
$\begingroup$

Let $a_{n}$ be the sequence recursively defined by $a_{0} = 1$, $a_{1} = -2$, and for $n\geq 2$, $a_{n}=-4 a_{n-1}-4 a_{n-2}$. Use strong induction to show that $a_{n}$ = $(-2)^n$ for all n.

This is what I have so far:

Basis:

  • $a_{0}=1=(-2)^0$
  • $a_{1}=-2=(-2)^1$

The statement is true when $n=0$ and when $n=1$.

Not sure how to go on from there.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Using the definition of strong induction,

Let $\displaystyle a_n=(-2)^n$ for $1\le n\le m$

$\implies \displaystyle a_{m+1}=-4a_m-4a_{m-1}=-4(-2)^m-4(-2)^{m-1}=-4(-2)^{m-1}(-2+1)=(-2)^2\cdot(-2)^{m-1}=(-2)^{m+1}$

$\endgroup$
5
  • $\begingroup$ I understand what is going on. But just for learning purposes can you explain what you are doing as you do the strong induction? $\endgroup$
    – Mark
    Nov 27, 2013 at 5:32
  • $\begingroup$ @Mark, please find link added in the answer $\endgroup$
    – lab bhattacharjee
    Nov 27, 2013 at 5:33
  • $\begingroup$ I don't understand the notation of the definition of strong induction. $\endgroup$
    – Mark
    Nov 27, 2013 at 5:34
  • $\begingroup$ @Mark, mathworld.wolfram.com/PrincipleofStrongInduction.html and mathworld.wolfram.com/PrincipleofStrongInduction.html $\endgroup$
    – lab bhattacharjee
    Nov 27, 2013 at 5:39
  • $\begingroup$ @Mark, induction is: show that the first domino falls, and that every domino that falls knocks the next one; then you can be sure all dominoes fall. Strong induction is, show that the first domino falls, and that if all dominoes up to a certain point fell, then the next one falls too. So, strong induction -although equivalent- allows you to use as argument a stronger assumption ("all dominoes up to a point") to prove that the next one also falls. Stronger assumptions make proofs easier. $\endgroup$
    – carlosayam
    Oct 2, 2014 at 12:10

You must log in to answer this question.

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