1. ## Tricky induction proof

I just can't see to figure this out.

Consider function $\displaystyle h$ as follows:

$\displaystyle \bullet \ h(1) = h(2) = 1$
$\displaystyle \bullet \ h(n) = h(n-1)^2 + h(n-2)\mbox{ for }n > 2$

Prove by induction that for all $\displaystyle n > 5$ that $\displaystyle h(n)$ and $\displaystyle h(n-1)$ are relatively prime.

2. Originally Posted by VENI
I just can't see to figure this out.

Consider function $\displaystyle h$ as follows:

$\displaystyle \bullet \ h(1) = h(2) = 1$
$\displaystyle \bullet \ h(n) = h(n-1)^2 + h(n-2)\mbox{ for }n > 2$

Prove by induction that for all $\displaystyle n > 5$ that $\displaystyle h(n)$ and $\displaystyle h(n-1)$ are relatively prime.
If give you a hint to get you started. Say that $\displaystyle h(n)$ and $\displaystyle h(n-1)^2$ where not relatively prime then there is a prime $\displaystyle p$ so that $\displaystyle p$ divides $\displaystyle h(n)\text{ and }h(n-1)$. However, $\displaystyle h(n) - h(n-1)^2=h(n-2)$ and so $\displaystyle p$ would divide $\displaystyle h(n-2)$. Which means that $\displaystyle p$ a common factor for $\displaystyle h(n-1)\text{ and }h(n-2)$. Thus, we have shown is that if $\displaystyle h(n)\text{ and }h(n+1)$ are relatively prime then $\displaystyle h(n+1)\text{ and }h(n+2)$ must be relatively prime.