$h$ is defined as follows: $ h(1) = h(2) = 1; h(n) = (h(n-1))^2 + h(n-2)$ if $n > 2$.
Prove that for all n>1 that the $gcd(h(n), h(n-1)) = 1$.
My attempt with proof by induction:
Let $P(n)$ be the statement that $gcd(h(n), h(n-1)) = 1$.
$P(2)$ is true because $gcd(h(2),h(1)) = gcd(1,1) = 1$
Assume $P(n)$. We shall prove $P(n+1)$.
We know that gcd(a,b) = gcd(b,r) if there exists q and r ints such that a = bq+r .
Thus, $gcd(h(n+1),h(n)) = gcd(h(n),h(n-1)),$ where $h(n+1) = a$, $h(n) = b$, and $h(n-1) = r$.
(from the function definition seemed to fit $a=bq+r$, with $b=q$)
By the inductive hypothesis, $gcd(h(n), h(n-1)) = 1$
Hence, P(n+1) is True.
Any flaws?
Assume that $d>1$ divides both $h(n)$ and $h(n-1)$. Then from the function definition, $d$ divides $h(n-2)$. Then it divides $h(n-3)$ and so on, you go back as much as needed... finally $d$ divides $h(1)$ which is $1$. Contradiction (since $d>1$).