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 the middle numbers in the triangle in terms of $x$, where each middle number is the $(x+1)th$ number in the $(2x+1)th$ row?

(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 fits. ) 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 such 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
1  
For reference: numerators are oeis.org/A157933 and center term numerators appear to be oeis.org/A033504 . –  Matthew Conroy Mar 5 '12 at 22:49
    
I think it is clearer if you count rows from zero, position along the row from zero, and eliminate the denominators. Then your recurrence becomes $A_{n,0}=A{n,n}=2^{n+1}-1, A_{n,r}=A_{n-1,r-1}+A_{n-1,r}+2^n$ –  Ross Millikan Mar 5 '12 at 23:06
    
I agree that an answer that fits is less valuable than an answer that explains, so: have you had a look at the links that Matthew and I have given, and at the links given at those links? –  Gerry Myerson Mar 6 '12 at 2:54
    
Indeed. I have tinkered with those, but while they fit, I can't see why they work. Any hints in any direction would be great. –  Ali Mar 6 '12 at 3:09
    
Please be more careful with parentheses. When you write 15a+ 25b+25c+15d/8 I suspect you mean (15a+ 25b+25c+15d)/8. They are not the same. –  Ross Millikan Mar 6 '12 at 3:46

2 Answers 2

up vote 1 down vote accepted

I guess the way to do this is to first consider the pyramid where we are doing this operation but not adding 1 at each stage. This gives us basically Pascal's triangle with the nth row divided by $2^n$. Now we note that the pyramid in the question can be obtained by adding together multiple copies of this pyramid, with one copy starting from each point so to speak.

eg. for first 3 rows:

        1
    1/2    1/2
1/4    2/4    1/4

+

        0
    1      0
1/2    1/2    0

+

        0
    0      1
0      1/2    1/2

+

        0
     0     0
  1     0     0

+

        0
     0     0
  0     1     0

+

        0
     0     0
  0     0     1

=

        1
    3/2    3/2
7/4    10/4    7/4

Now for any point in the final pyramid, we can look at the constituent pyramids that contribute to it, and the value it gets from each pyramid. For the midpoint, the head of the constituent pyramids whose contributions are non-zero form a diamond, and it is easy to see by examination that the values they contribute form the same set as the values they have in the constituent pyramid rooted at the top. eg. consider contributions to

66/16 in

                                 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

by

                **1**
           **1/2    1/2**
        **1/4    2/4    1/4**
    1/8    **3/8    3/8**    1/8
1/16   4/16   **6/16**   4/16   1/16

Only the points that I have put in bold have the pyramids rooted at them contribute, moreover the pyramid rooted at 1 contributes 6/16, the one rooted at 6/16 contributes 1, ones rooted at 1/2 contribute 3/8, etc. (so list of contributions by each point in this diamond can be obtained simply by flipping the diamond of values here vertically then horizontally, although the horizontal flip won't change the values). So the value we want here is sum of values in this diamond = $1 + (1/2 + 1/2) + (1/4 + 2/4 + 1/4) + (3/8 + 3/8) + 6/16$, which gives $66/16$ like we want.

So in general, we can just look at the initial contributing pyramid, make a diamond like this, and then sum the values in the $2x+1$ rows. The first $x+1$ sums will simply be 1 each, after that at the nth row we will need to look at sum from k going from $n-(x+1)$ to $x$ of $^nC_k/2^n$. So overall sum we require is $x + 1 + \sum_{n=x+2}^{2x+1}\sum_{k=n-(x+1)}^{x}^nC_k/2^n$. I did not try to simplify this as the simplified answer seems to have been provided by Gerry already.

share|improve this answer
    
I had a similar idea about pursuing it with pascal's triangle. One question: what do $n$ and $k$ signify and what do you mean by $x$ of$ ^nC_k/2^n$? –  Ali Apr 11 '12 at 16:18
    
and in your explanation what is x? –  Ali Apr 11 '12 at 16:18
    
what do you mean by x of $^nC_k/2^n$? What are x, n, and k here? Could you explain a bit further? –  Ali Apr 13 '12 at 15:22
    
Sorry, did not check this for some time. 2x+1 is row number of the term we want in the actual pyramid. n is the row number in the summation. k is element number in the row. Thanks for accepting the answer btw. –  Wonder Apr 16 '12 at 11:25
    
Thank you. I have been thinking, using k, and n, could we find some generalization for the kth number in the nth row? Would you be up to the challenge? :) –  Ali Apr 17 '12 at 15:51

I think it may be http://oeis.org/A033504, where the formula $$4^{-n}(n+1)\left(2^{2n+1}-{2n+1\choose n+1}\right)$$ is attributed to Vladeta Jovovic. E.g., when $n=3$, this gives $372/64$, which is the next term.

share|improve this answer
    
But that applies to the centerpieces on odd rows. We speak of the centerpieces on even rows. –  Ali Mar 5 '12 at 23:16
    
I thought we were talking about the numbers $1$, $10/4$, $66/16$, $372/64$, etc. If you are talking about the numbers $3/2$, $25/8$, $154/32$, you should probably look at the first link in Matthew's comment. –  Gerry Myerson Mar 6 '12 at 0:29

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.