Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed.

Suppose we have a triangle of numbers. Atop the triangle is 1: each number below it is determined by summing half of each of the numbers that it is supporting, and adding 1 to the sum. The first few layers in the triangle look like this:

                                 1
                            3/2     3/2
                       7/4     10/4     7/4
                  15/8    25/8      25/8    15/8 
            31/16     56/16    66/16    56/16   31/16

The numbers on the edges are such that the number on either end of layer n is $\frac{2^n -1}{2^{n-1}}$. Can we write a generalization for any term in the pyramid, given that any term is the $k$th term in the $n$th row?

Original question and proof for middle term here: A pyramid of numbers

There is also this: Proof- central term of recursive pyramid

Perhaps a similar method could be used?

(Please explain the architecture of your solution, and how you came about it. I think that an answer that simply fits is FAR less valuable than an instance where we know WHY the answer is fitting. ) Perhaps this can be done with modifications to Pascal's triangle?


I have noticed something rather interesting- if we discard the denominators of the numbers in this pyramid, which are simply $2^{n-1}$ where $n$ is the row number, and leave all the numerators behind in the pyramid, then we can produce the nth line of the pyramid by taking the following pyramid(the following is a example, that produces the fourth line of the pyramid)

      j  
    h   i  
  e   f   g  
a   b   c   d  

If e= $\frac{a+b}{2}$, f= $\frac{b+c}{2}$, and so on and so forth, all characters in rows above the bottom one are the "average" of the two characters they are nested in. Then if we add a+b+c+d+e+f+g+h+i+j, we get 15a+ 25b+25c+15d/8. As you can see, the coefficients produce the fourth line in our pyramid. Similarly if we add the characters in a pyramid with base [abcde] and tip k we will get 31a+56b+66c+56d+31e/16 . The coefficients of a,b,c,d, and e are the terms in the fifth line of our pyramid. Can anyone think of WHY(what in the architecture of both pyramids) this correlation exists between these two seemingly disconnected pyramids, through connecting their production methods?

share|improve this question
3  
Are you aware of this closely related question? –  joriki Apr 20 '12 at 1:17
    
@joriki I am. But that is a proof for the closed form of the other related question I posted. A generalization would be fantastic. –  Ali Apr 20 '12 at 12:30
    
In the future, it would be good style to link to such closely related questions if you're aware of them; otherwise a lot of effort might be unnecessarily duplicated. –  joriki Apr 20 '12 at 12:54
    
Fixed. Any ideas? –  Ali Apr 20 '12 at 17:48
    
possible duplicate of Proof- central term of recursive pyramid –  Pedro Tamaroff Apr 20 '12 at 18:59
show 1 more comment

1 Answer 1

up vote 4 down vote accepted
+50

Let $n=0$, $1$, $2$, ... label the rows, and $k=0$, $1$, ..., $n$ label the entries in a row. Redefine the entries by multiplying each row by $2^n$ to eliminate fractions. Each entry in row $n$ of this redefined triangle is obtained by summing the entries to the left and right in row $n-1$ and then adding $2^n$. Extend each row two steps to both left and right using the same recurrence:

            -2   0    1   0  -2
           -4   0   3   3   0  -4
          -8   0   7  10   7   0  -8
        -16   0  15  25  25  15   0  -16
       -32   0  31  56  66  56  31   0  -32

Having to add $2^n$ is an annoyance. If we form differences of consecutive row entries, this feature is eliminated, and we get a new triangle that satisfies the usual Pascal's triangle recurrence:

            2   1  -1  -2
          4   3   0  -3  -4
        8   7   3  -3  -7  -8
     16  15  10   0 -10 -15 -16
   32  31  25  10 -10 -25 -31 -32

If we form difference of consecutive row entries a second time, we get the negation of Pascal's triangle itself:

             -1  -2  -1
           -1  -3  -3  -1
         -1  -4  -6  -4  -1
       -1  -5 -10 -10  -5  -1
     -1  -6 -15 -20 -15  -6  -1

The entries in this third triangle are $-\binom{n+2}{k}$. (Remember the top row is row 0; we let $k$ range from 0 to $n+2$.) Therefore the entries in the second triangle are $$ 2^{n+1}-\sum_{j=0}^k\binom{n+2}{j}, $$ where we let $k$ range from $-1$ to $n+2$.

Finally, the entries in the first triangle are $$ -2^{n+1}+\sum_{i=-1}^k\left[2^{n+1}-\sum_{j=0}^i\binom{n+2}{j}\right]=(k+1)2^{n+1}-\sum_{j=0}^k(k-j+1)\binom{n+2}{j}, $$ where we let $k$ range from $-2$ to $n+2$. Therefore the entries in the original triangle are given by $$ 2(k+1)-2^{-n}\sum_{j=0}^k(k-j+1)\binom{n+2}{j}. $$ Mathematica writes the sum in terms of a hypergeometric function: $$ 2(n-k+1)-2^{-n}\binom{n+2}{k+2}\,_2F_1(2,k-n;k+3;-1). $$

share|improve this answer
    
This is rather nice- what is $j$, though? –  Ali Apr 22 '12 at 17:33
1  
Both the $i$ and the $j$ that appear in several formulas are summation indices, so they don't appear once the sum has been evaluated. In other words, they are dummy variables. The reason for the summation is that we are reconstructing a sequence from its differences. So if you have a sequence $a_0$, $a_1$, $a_2$, ..., with differences $d_1=a_1-a_0$, $d_2=a_2-a_1$, and so on, then knowing $a_0$, and $d_1$, $d_2$, ... allows you to compute $a_1$, $a_2$, ... Specifically, $a_1=a_0+d_1$, $a_1=a_0+d_1+d_2$, and in general, $a_k=a_0+\sum_{j=1}^k d_k$. This principle has been applied two times. –  Will Orrick Apr 22 '12 at 17:53
add comment

Your Answer

 
discard

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.