Fibonacci Like Sequence I'm working on this problem but I'm not sure how to solve it.
Consider a sequence of positive integers $1, a_2, a_3, \dots , a_k=55$ where each term in the sequence is the sum of any two previous (not necessarily distinct) terms. What is the smallest value of $k$ such that the sequence exists?
Just for clarification, a possible sequence would be $1, 2, 4, 8, 16, 32, 48, 52, 54, a_{10}=55$, where the second through sixth terms are created by adding the previous term twice, the seventh term is created by adding 16 to the previous term, the eighth term is created by adding 4 to the previous term, the ninth term is created by adding 2 to the eighth term, and 55 is created by adding 1 to the ninth term. This sequence would have $k=10$.
I found a possible sequence for $k=9$, which is $1, 2, 4, 6, 12, 24, 48, 54, 55$, and I'm pretty sure I can't find one for $k=8$. However, I'm not sure how to prove that $k=9$ is the lowest I can go. Thanks for any help on this problem.
 A: A proof, though not satisfying, is to perform breath-first search over all sequences. I verified that $k = 9$ is indeed the shortest possible sequence, for which there are $215$ sequences ending at $55$. Here are the sequences, and here is my code.
Maybe someone can find a clever proof :)
A: Partial and unhelpful answer:   $55 = 110111$ in binary.  So we can get an upper bound on $k$ by doubling till we get to $2^5$.  Then add numbers two at a time till we have all the ones we need in the binary expansion of $55$.
In binary:
$$a_1 =1, a_2=10, a_3=100, a_4=1000, a_5=10000, a_6=100000$$
(we'll have to re-order when we're done) then:
$$a_7=11, a_8=111, a_9 = 110000, a_{10}=110111.$$
So we need a term of the sequence for each power of two up to $2^5$ that is $5= \lfloor \log_2 55 \rfloor$ terms.  Then we need some more terms depending on how many binary digits there are.  If there are $m$ digits, it will take (I think) $m-1$ more terms.
(Or maybe $2^{\lceil log_2 m$ \rceil} $ more terms.)
I just toss this out there because 1. I'm really busy grading papers just now but 2. Maybe the binary idea will be helpful.
