A sequence is defined recursively as follows: and
So, for example, , . Prove that for all positive integers ,
Solutions — 2
Solution 1
Introduce a new sequence . We have and the given recursion translates into
We have to prove that . As , the recursion easily implies that for all .
Let us now show by induction that . The start at is clear, as . Assume now that the inequality holds true for , i.e. . This assumption implies
Solution 2
The sequence begins , and helped by the occurrence of in the statement of the question, we check that the sequence begins , and we note the pattern in the form of the numerators and denominators of the terms . We therefore conjecture
We prove the conjecture by simple induction. The formula is trivial for . Assuming the validity of the conjecture for , we have
as asserted. This proves the conjecture. It now follows immediately that and that
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.