# Summing the cubes of the insertion sequence

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?

-
Please provide a more self-contained description of the sequence. Are you referring to oeis.org/A002487? It seems to me unlikely to have a simple formula for the sum of the cubes-what is the motivation? –  Ross Millikan Nov 17 '11 at 22:01
The duplicate does not have a self-contained question and it does not have an answer, though. –  Phira Dec 4 '11 at 15:13
If this is homework, then context can be useful, for example, why do you consider this question to be linear algebra? –  Phira Dec 4 '11 at 15:25
I just thought it was linear algebra - quite possible I'm wrong as it happens I don't know where does some problem belong. If so, sorry. And not too much context, either - just one of the problems we were given by our prof during the optional classes (preparing for competitions and such). –  George Shack Dec 4 '11 at 15:35
@Gerry: Thanks for catching that. I've now merged the old one to here. –  Zev Chonoles Dec 4 '11 at 23:11

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.

-
Brilliant, thank you! –  George Shack Dec 7 '11 at 15:01

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}$.

-
Actually, I need the um of cubes of elements of each row. –  Chris Nov 18 '11 at 18:31
How does the "um of cubes" differ from the sum of cubes? –  Robert Israel Nov 20 '11 at 2:47
Please excuse my spelling. My keybord is a bit fawlty. Could you show me how you came to this solution? –  Chris Nov 21 '11 at 20:08
I don't have a proof, it's just from looking at the numbers. –  Robert Israel Nov 22 '11 at 6:06
Is it possible to prove it by induction? If so, could you give me a hint on how it can be done? –  Chris Nov 22 '11 at 18:01
Not a solution, but some help. The recurrence on the number of entries is $M(m)=2M(m-1)-1, M(1)=2$. This shows line $m$ has $(2^m+2)/2$ entries. The order doesn't matter, just the quantity of each value: line 3 has (as you say) two $1$'2, a $2$, and two $3$'s. The sums of cubes go 2,10,64,442,3088, which appears (without the 2) as A199487 as $9*7^m+1$. Maybe you can prove this recurrence.