# Tricky induction proof

• Feb 17th 2009, 08:42 PM
VENI
Tricky induction proof
I just can't see to figure this out.

Consider function $h$ as follows:

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

Prove by induction that for all $n > 5$ that $h(n)$ and $h(n-1)$ are relatively prime.
• Feb 17th 2009, 10:37 PM
ThePerfectHacker
Quote:

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

Consider function $h$ as follows:

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

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

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