# Induction!

• Mar 7th 2008, 02:48 PM
CSkyle
Induction!
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
• Mar 7th 2008, 03:58 PM
galactus
The characteristic equation is $\displaystyle a^{2}-2a-1=0$

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

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

Use the initial conditions to solve:

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

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

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

Therefore, we have:

$\displaystyle 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.
• Mar 7th 2008, 04:10 PM
PaulRS
$\displaystyle a_1=1$; $\displaystyle a_2=1$ and $\displaystyle a_n=2\cdot{a_{n-1}}+a_{n-2}$

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

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

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

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

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