BdMO Online Forum

Find (with proof) the length of the longest arithmetic subsequence of the Fibonacci sequence.
$\small\textbf{Source:}$ Self-made, but probably well-known by now.

I'm assuming that by 'subsequence' you mean the terms have to be consecutive terms of Fibo-Seq.

If there are at least $3$ terms then $F_{n+2}-F_{n+1}=F_{n+1}-F_{n}\Rightarrow 2F_{n+1}=F_n+F_{n+2}$ since common difference of consecutive terms is equal. Using $F_{n+2}=F_{n+1}+F_n$ this reduces to $F_{n+1}=2F_n$ which again reduces to $F_n=F_{n-1}$. So we must have $F_{n-1}=F_n=1$ and the longest subsequence is $1,2,3$.

But subsequence does not necessarily need to be of consecutive terms of the original sequence, does it?

Samiun Fateeha Ira wrote:But subsequence does not necessarily need to be of consecutive terms of the original sequence, does it?

Clearly $F_{m}-F_{n}>F_{n+2}-F_{n}>F_{n}-1>F_{n}-F_{k}$ for all $m\geq (n+2), k\leq (n-1)$. This means $F_{n+1}$ is the only possible term which can be in an arithmetic sequence with $F_{n}$ and $F_{k}$ where $k<n$.
Am I right?

Samiun Fateeha Ira wrote:But subsequence does not necessarily need to be of consecutive terms of the original sequence, does it?

A substring of a string is any portion cut off from the string, so... I'm not quite sure about what is meant here by subseq.

Nirjhor wrote:A substring of a string is any portion cut off from the string, so... I'm not quite sure about what is meant here by subseq.

In math (and programming), a sequence is called a subsequence of another sequence if all of its terms appear in the same order (but not necessarily consecutive) in the other sequence. Example: $F_1,F_3,F_4,F_{10}$ is a subsequence of the Fibonacci sequence but $F_2,F_1,F_4$ isn't.

@Sanzeed, yes you are. Your procedure proves there can be only one type of arithmetic subsequence, namely $F_n,F_{n+2},F_{n+3}$