I think I have found the general expression for .
Let ... be a seqence of positive integers for which
Prove that and are relatively prime for every nonnegative integer .
...
...
...
There doesn't seem to be a discernable pattern, but any how, I think these can be approached by Strong Induction.
The basis case is easy. is obvious.
The Inductive step: Assume . We show that ,
I can't see the recurrence relation for . Need help.
This sequence is Stern's Diatomic Series.
Stern's Diatomic Series is defined as
Now for the proof, base case: .
Assume for all .
Case 1: which gives .
By the IH, there exists such that
Therefore
Case 2: which gives .
By the IH, there exists such that
Therefore
So by strong induction the claim for all holds.