Induction!

**CSkyle** · March 7th 2008, 02:48 PM

I'm not sure how to go about setting up the steps for this problem.

a1 = 1, a2 = 1 and an = 2an-1 + an-2 for all n ≥ 3. prove an is odd for all n≥1.

first six are 1,1,3,7,17,41

I could also use help on another problem...
proving (3,5,7) is the only prime triple - consecutive odd integers which are all prime -

to do this i prove that for any odd integer k, one of the integers 2k+1, 2k+3, and 2k+5 must be divisible by 3.

I know i need to use cases for this.

how does this then show that (3,5,7) is the only prime triple?

thanks for the input guys.

kyle

**galactus** · March 7th 2008, 03:58 PM

The characteristic equation is $a^{2}-2a-1=0$

It has solutions $a=\sqrt{2}+1, \;\ a=1-\sqrt{2}$

$b(\sqrt{2}+1)^{n}+c(1-\sqrt{2})^{n}$

Use the initial conditions to solve:

$1=b(\sqrt{2}+1)+c(1-\sqrt{2})$

$1=b(\sqrt{2}+1)^{2}+c(1-\sqrt{2})$

Solve the system and get $b=\frac{\sqrt{2}-1}{2}; \;\ c=\frac{-(\sqrt{2}+1)}{2}$

Therefore, we have:

$a_{n}=(\frac{\sqrt{2}-1}{2})(\sqrt{2}+1)^{n}+(\frac{-(\sqrt{2}+1)}{2})(1-\sqrt{2})^{n}$

Now, perhaps you can use this to prove the solutions are always odd.

**PaulRS** · March 7th 2008, 04:10 PM

$a_1=1$ ; $a_2=1$ and $a_n=2\cdot{a_{n-1}}+a_{n-2}$

We have the base cases, so we'll go to the inductive step

Suppose $a_{n-1}$ and $a_{n-2}$ are odd, we shall prove that $a_n$ is also odd

Indeed, $a_n=2\cdot{a_{n-1}}+a_{n-2}\equiv{2\cdot{1}+1}\equiv{1}(\bmod.{2})$

Or if you prefer: $a_{n-1}=2a+1$ and $a_{n-2}=2b+1$ ( $a$ and $b$ are natural numbers)

So $a_n=2\cdot{(2a+1)}+2b+1=2(2\cdot{a}+b+1)+1$ an odd number

Thread: Induction!

LinkBack

Thread Tools

Display

Induction!

Similar Math Help Forum Discussions

Strong induction vs. structural induction?

Rigorously prove the principle of complete induction from mathematical induction??

induction help

Mathemtical Induction Proof (Stuck on induction)

induction

Search Tags