Originally Posted by

**emakarov** That's not the response I was hoping for. Look at the first two lines. The first line defines U at 1 and 2. The second line defines U at 3 when n = 2. Indeed, the right-hand side refers to U(2) and U(1), which are already defined. Similarly, it defined U at 4 when n = 3, and in general it defines U at every n ≥ 2. So, what can the third line add? At best it agrees with what the first two lines say; at worst it contradicts them. But it is not a part of the definition; it is a separate claim. It turns out that this claim is true and is given as a lemma without a proof to be used in this problem.

Not knowing the definitions involved in a statement is worse than not being able to prove that statement, but here are further hints anyway. Replace U(n+p) with U(n) * U(p-1) + U(n+1) * U(p) in GCD(U(n+p), U(n)) and use the following facts.

Proposition 1. GCD(kn + m , n) = GCD(m, n) for k ∈ ℤ.

Proposition 2. GCD(U(n+1), U(n)) = 1. Proof: By induction on n.

Proposition 3. If GCD(m, n) = 1, then GCD(km, n) = GCD(k, n).