Three Counting Questions Let $S_1$ denote the sequence $(1,1)$.
For $n\ge 1$, we build a sequence $S_{n+1}$ by copying sequence $S_n$, inserting blanks between consecutive terms, and filling each blank with the sum of the two terms it's between. Thus we have
\begin{align*}
S_2 &= (1,\underline{2},1),\\
S_3 &= (1,\underline{3},2,\underline{3},1),\\
S_4 &= (1,\underline{4},3,\underline{5},2,\underline{5},3,\underline{4},1),
\end{align*}
and so on.


*

*What is the sum of all entries in $S_7$?

*What is the largest entry in sequence $S_{11}$?

*What fraction of the terms of $S_{64}$ are odd?

 A: Let $T_n$ represent the total of all elements of $S_n$. Each of the elements of $S_{n-1}$ contributes twice to the new elements of $S_n$ except for the first and last elements, which contribute once each, and are always $1$. So $T_n = 3T_{n-1}-2$.
$$
T_n = \{2,4,10,28,\dots\} = 3^{n-1}+1 
$$
So $T_7  = 3^6+1 = 730$
The largest entry in a set is always between the two entries that were largest in the previous two sets. so this is just an offset Fibonacci number. Therefore the largest entry in $S_{11} = F_{12} = 144$
Let $E_n$ denote the count of even numbers in the sequence. At each step from $S_n$ to $S_{n+1}, 2^{n-1}$ numbers are added of which $2E_n$ are odd, and the rest even.
So $E_n=\{0,1,1,3,5,11,21,43, \ldots\}$
The pattern of odd/even elements looks like $o[oeo]^*o$ for odd $n$ and $[oeo]^*$ for even $n$.
For even $n$, the proportion of even numbers is always exactly one-third. So two-thirds of the terms of $S_{64}$ are odd.
A: Hints: For the sum, you should be able to write a recurrence for the sum.  Each element except the $1$'s at the end gets added   
For the maximum element, note that the maximum element in $S_i$ is next to one of the maximum elements of $S_{i-1}$.  If you compute a couple more lines the maximum elements should look familiar.  
For the fraction of even elements, note that you can never have two even elements in a row.  Each even number creates two more odd numbers.  All the rest of the new numbers are even.
