We consider the sequences and which are defined by and and by
for .
Decide whether there are infinitely many integers which occur in both sequences.
Austria competition problems
Solution
Answer. Yes.
Sequence starts with values , , , , , . Sequence starts with values , , , , , , , . We therefore conjecture that holds for .
Shifting the recurrence yields
for . Multiplying these recurrences by , and , respectively, and taking the sum yields and thus
for .
Shifting the recurrence of yields
for . Multiplying these recurrences by , , , and , respectively, and taking the sum yields and thus
for .
We see that the subsequences and have the same initial values and and fulfil the same recurrence. This implies that for all .
From the given recurrence, it is obvious that the sequence is strictly increasing. Thus we also get infinitely many values which occur in both sequences.
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.