Hard sequence

[Marina19]

There is a given sequence (1,1) from which we create new by adding new element between every pair of numbers being a sum of these two. We start from (1,1) after first step we get (1,2,1), after second (1,3,2,3,1) etc. For every n>0 find the sum of the cubes of the elements from the sequence after n steps.

So S(1) = 10
S(2) = 64
...

[Marina19]

Hello again!

I've got the answer but I want you to help me in finding out why it is true...

The answer is

\[S(n)=7^{n-2}* 63 +1\]
(1,1)
(1,2,1) \[7^{-1}*63 +1 = 10 =1^{3} + 2^{3} +1^{3}\]
(1,3,2,3,1)\[7^{0}*63 +1 = 64 =1^{3}+3^{3} + 2^{3}+3^{3} +1^{3}\]

(1,4,3,5,2,5,3,4,1) S(3) = 7 *63 + 1 = 442

[Corei13]

Nice problem!
$[0]=(1,1)$
$[1]=(1,2,1)$
$[2]=(1,3,2,3,1)$
.
.
.
$[n]=(a_1, a_2, a_3, \cdots , a_m)$
$S(n) = a_1^3 + a_2^3 + \cdots + a_m^3$
$T(n) = a_1 a_2 (a_1+a_2) + a_2 a_3 (a_2+a_3) + \cdots + a_{m-1}a_m ( a_{m-1}+a_m )$
$c_n = S(n)+T(n) - 1$
Note that, $[n+1]=(a_1, a_1+a_2,a_2,a_2+a_3,\cdots,a_{m-1},a_{m-1}+a_m, a_m)$ and $a_1=a_m=1$
Straightforward calculation gives,
$S(n+1)=S(n) + \sum{( a_i + a_{i+1})^3}$
$=S(n) + 2S(n)+3T(n)- a_1 ^3 - a_m^3$
$=3(S(n)+T(n))-2$

And,
$T(n+1)$
$=\sum{\left( a_i (a_i + a_{i+1} )(2a_i + a_{i+1}) + (a_i +a_{i+1})a_{i+1}(a_i + 2a_{i+1}) \right) }$
$=2\sum{\left(a_i^3 + a_{i+1}^3\right)} + 4\sum a_i a_{i+1} ( a_i + a_{i+1} )$
$=2(2S(n)-a_1^3 -a_m^3)+4T(n)$
$=4(S(n)+T(n))-4$

So, $c_{n+1}=S(n+1)+T(n+1) - 1=7(S(n)+T(n))-7=7c_n$
or, $c_{n+1}=7^{n+1} c_0$
But, $S(0)=1^3 + 1^3 = 2, T(0)=1\cdot1\cdot(1+1)=2$ so, $c_0=3$
And so, $c_{n+1}=3\cdot7^{n+1}$ or, $c_{n-1}=3\cdot7^n$
or, $S(n+1)=3(S(n)+T(n))-2=3(c_n+1)-2=9\cdot7^n+1$
That is, $S(n)=9\cdot7^{n-1}+1$!