Stern's sequence [duplicate]
Having a finite sequence of numbers given, we create a new sequence by inputting in each step between every pair of two adjacent numbers a new number equal to their sum. We start with (1,1), in the second step we have (1,2,1), in the third (1,3,2,3,1) etc. For every $n\geq1$ calculate the sum of the cubes of the numbers being part of the sequence acquired in the nth step.
I thought that what we know is that in every step, for a sequence of lenght n we'll get n-1 new numbers being the sums of the adjacents so the next sequence will be 2n-1. The sum of the first is $1^3+1^3=2$, then we have $1^{3}+2^{3}+1^{3}=2+8=10$, then the_sum_so_far$+2*3^{3}$. The useful property is that the sequence is symmetrical having some k pairs of numbers on both sides of the central 2 and always has an odd amount of numbers - only the first step is even. Also, after some playing with numbers, I determined the sum will be $9*7^{n-2}+1$ for $n\geq2$ but have no idea on how to prove this... Could you please help?
Here’s a complete solution.
It’s convenient to represent each new number as the ordered pair of its left and right parents. The first new number is $2$, represented by $\langle 1,1\rangle$. The next two are both $3$, represented by $\langle 1,2\rangle$ and $\langle 2,1\rangle$. At the next step there are four new numbers, $4,5,5,4$, represented respectively by $\langle 1,3\rangle$, $\langle 3,2\rangle$, $\langle 2,3\rangle$, and $\langle 3,1\rangle$. Of course each new number is simply the sum of its parents, so $\langle m,n\rangle$ always represents $m+n$. It’s also clear that $\langle m,n\rangle$ is the right parent of $\langle m,m+n\rangle$ and the left parent of $\langle m+n,n\rangle$. Let’s follow the descendants of $\langle m,n\rangle$ and their cubes for a few generations.
From $\langle m,n\rangle$ we get $\langle m,m+n\rangle$ and $\langle m+n,n\rangle$, corresponding to $2m+n$ and $m+2n$, the sum of whose cubes is $9(m^3+2m^2n+2mn^2+n^3)$. These produce $\langle m,2m+n\rangle$, $\langle 2m+n,m+n\rangle$, $\langle m+n,m+2n\rangle$, and $\langle m+2n,n\rangle$, corresponding to $3m+n$, $3m+2n$, $2m+3n$, and $m+3n$, the sum of whose cubes is $7\cdot9(m^3+2m^2n+2mn^2+n^3)$.
If we call $\langle 1,1\rangle$ the first generation, $\langle 1,2\rangle$ and $\langle 2,1\rangle$ the second generation, and so on, the calculation in the preceding paragraph implies that for $k\ge 2$, the sum of the cubes of the numbers in the $(k+1)$-st generation is $7$ times the sum of the cubes of the numbers in the $k$-th generation.
The sums of the cubes in the first two generations are $8$ and $54$, so for $k\ge 2$ the sum of the cubes in the $k$-the generation is $s_k = 54\cdot7^{k-2}$. Recall, however, that these totals are the sums of the new cubes at each stage of the original problem. Let $t_k$ by the sum of the cubes at stage $k$ in the original problem. Then $t_{k+1}=t_k+s_k$ for $k\ge 1$, where $t_1=2$. Thus, $t_1=2$, $t_2=2+8=10$, and $$t_{k+1}=t_k+s_k=t_k+54\cdot7^{k-2}$$ for $k\ge 2$. In other words, for $k\ge 2$ we have
$$\begin{align*} t_{k+1}&=t_2+\sum_{i=0}^{k-2}\left(54\cdot7^i\right)\\ &=10+54\cdot\frac{7^{k-1}-1}6\\ &=10+9\left(7^{k-1}-1\right)\\ &=1+9\cdot7^{k-1}\;. \end{align*}$$
This formula also yields the correct value when $k=1$, so after shifting the index we have $t_k=1+9\cdot7^{k-2}$ for all $k\ge 2$, as desired.
If you want the sums of the cubes of the elements of each row [1] [1,2] [1,3,2,3] [1,4,3,5,2,5,3,4] etc, that sequence is
1, 9, 63, 441, 3087, 21609, 151263, 1058841, 7411887, 51883209, 363182463, 2542277241, 17795940687, 124571584809, 872001093663
where it appears the $n$'th term for $n \ge 2$ is $9 \times 7^{n-1}$.