Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Please provide a more self-contained description of the sequence. Are you referring to 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
up vote 4 down vote accepted

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.

share|cite|improve this answer
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}$.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.