Question: The Fibonacci sequence is a sequence of natural numbers $A_1,A_2,A_3,...$ defined as follows: $A_0 = 0, A_1 = 1$, and for all $n ≥ 2, A_n = A_{n−1} + A_{n−2}$ The 1st few numbers of the sequence are $0, 1, 1$.
Prove that for all $n$ in naturals, $\gcd(A_n,A_{n+1}) = 1$. Try using using these claims.
$∀n ∈N, \gcd(0,n) = n$ , $∀p,q,n,a,b ∈Z, n | a∧n | b ⇒ n | ap + bq$
You must use contrapositive somewhere within the proof.
Induction Attempt:
$P(n)\iff \gcd(A_n,A_{n+1}) = 1.$
Base Case. $P(0)$ will be shown true. Because $0$ is a natural, let $n = 0$ and $(A_2, A_1) = 1$ because of previously proven claims.
Induction
$∀k∈N \gcd(A_k, A_{k+1}) = 1$ we need to prove
$p(n) ⇒p(n+ 1)$ that is, $∀k∈N \gcd(a_{k+1}, a_{k+2} = 1$
inductive step.
Take the contrapositive(required) $-P(n+ 1) ⇒-P(n)$ then, $(∃n∈N, n >1∧cd(A_{n+ 1}, A_{n+ 2})) ⇒(∃n∈N, n >1∧cd(A_n, A_{n+ 1}))$
Now do I just find and plug in #s for the existential quantifier that work? Or how do you complete it(its about done right?) Why would it be $cd$ as opposed to $\gcd$ above and is the $n>1$ necessary ?
If $d | A_{n+1}$ and $d | A_{n}$ then $d | ( A_{n+1}-A_{n}) \implies d | A_{n-1} $.
Work your way down to $d | A_1 = 1 $.
If you want to use induction, your theorem is:
If $d | A_{n+1}$ and $d | A_{n}$ then for $ k \ge 1$ $d | A_{n-k}$.
We showed it for $k=1$ and the same method allows us to go from $k$ to $k+1$.
Note that this is not standard induction but what I call moderately strong induction in that the truth for $k-1$ and $k$ is required to go from $k$ to $k+1$.
Then set $k = n$ and we have $d | A_0$ so $d = 1$.