Proof- central term of recursive pyramid

Question

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

How can we prove $4^{-n}(n+1)\left(2^{2n+1}-{2n+1\choose n+1}\right)$ produces the central term in the $2n+1$th row of the following pyramid? The pyramid is produced in this way: atop the triangle is 1 and each number below it is determined by summing half of each of the numbers that it is supporting, and adding 1 to the sum.

                             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

I have attempted induction and it does not work well as I am sure you can see. I do not know how to prove the formula... even an intuitive proof would work.

Please see my comment below about constructing the pyramid as a whole using coefficients. Another question to all(ESP joriki) : what can be said in general about any term in the pyramid? Can we make a generalization of any term in the pyramid based on The row number and the $k+1$th or kth term in a row, perhaps, depending on how you define k? I have been looking at it and it seems that writing it in terms of k and z, where z=n-1 might make it simple, but I don't know.

Answer 1

Subtracting $n$ from the $n$-th row subtracts out the cumulative effects of adding $1$ to the entries; the result is a triangle of negative numbers that can be viewed as resulting from averaging negative values beyond the boundary. Multiplying the $n$-th row by $-2^{n-1}$ and extending the triangle yields:

7   5   3   1   0   1   3   5   7
 12   8   4   1   1   4   8  12
   20  12   5   2   5  12  20
     32  17   7   7  17  32
       49  24  14  24  49

Here each row is generated from the one above it by adding adjacent values. Thus the values are sums over all possible paths to the first row, weighted by the value at the endpoint in the first row. For the central values, this sum is by symmetry twice the sum for one half of the first row. Thus the value in the $2n+1$-th row is

$$a_{2n+1}=2\sum_{k=0}^{n-1}\binom{2n}{k}(2(n-k)-1)\;.$$

Since

$$\binom{2n}{k}k=\frac{(2n)!}{k!(2n-k)!}k=\frac{(2n)!}{(k-1)!(2n-k)!}=\frac{(2n-1)!}{(k-1)!(2n-k)!}2n=\binom{2n-1}{k-1}2n\;,$$

this is

$$a_{2n+1}=2(2n-1)\sum_{k=0}^{n-1}\binom{2n}{k}-8n\sum_{k=1}^{n-1}\binom{2n-1}{k-1}\;.$$

The sums are readily evaluated, since except for some missing terms they are half of $\sum_k\binom lk=2^l$:

$$ \begin{eqnarray} a_{2n+1} &=& 2(2n-1)\frac12\left(2^{2n}-\binom{2n}n\right)-8n\frac12\left(2^{2n-1}-2\binom{2n-1}{n-1}\right) \\ &=& 8n\binom{2n-1}{n-1}-(2n-1)\binom{2n}n-4^n \\ &=& 8n\frac{(2n-1)!}{n!(n-1)!}-(2n-1)\frac{(2n)!}{n!n!}-4^n \\ &=& \frac{(2n-1)!}{n!n!}\left(8n^2-2n(2n-1)\right)-4^n \\ &=& \frac{(2n-1)!}{n!n!}\left(4n^2+2n\right)-4^n \\ &=& \frac{(2n-1)!}{n!n!}2n(2n+1)-4^n \\ &=& \frac{(2n+1)!}{n!n!}-4^n \\ &=& \binom{2n+1}{n+1}(n+1)-4^n \end{eqnarray} $$

Then undoing the earlier transformations gives

$$ \begin{eqnarray} a_{2n+1}&=&-2^{2n}(c_{2n+1}+2n+1)\;, \\ c_{2n+1} &=&2n+1-2^{-2n}a_{2n+1} \\ &=& 2n+2-4^{-n}\binom{2n+1}{n+1}(n+1) \\ &=& (n+1)\left(2-4^{-n}\binom{2n+1}{n+1}\right) \\ &=& 4^{-n}(n+1)\left(2^{2n+1}-\binom{2n+1}{n+1}\right)\;. \end{eqnarray}$$

Answer 2

It appears that joriki has answered the original question. I got bogged down on that when I got sick, but I did manage to establish that $4^{-n}(n+1)\left(2^{2n+1}-{2n+1\choose n+1}\right)$ gives the expected number of tosses of a fair coin required to get either $n+1$ heads or $n+1$ tails, as I mentioned in the comments. It’s too long for a comment, but it might be of some interest, so here it is.

---

Suppose that we toss a fair coin until we get either $n+1$ heads or $n+1$ tails. Say that this happens on the $k$-th toss; clearly $n+1\le k\le 2n+1$. There are $\binom{k-1}n$ sequences that terminate with a head on the $k$-th toss and another $\binom{k-1}n$ sequences that terminate with a tail on the $k$-th toss. Each of these occurs with probability $2^{-k}$, so the expected number of tosses is

$$2\sum_{k=n+1}^{2n+1}2^{-k}k\binom{k-1}n\;.$$

To get rid of the negative exponents I’m going to multiply through by $2^{2n}$ to get

$$\begin{align*} 2^{2n+1}\sum_{k=n+1}^{2n+1}2^{-k}k\binom{k-1}n&=\sum_{k=n+1}^{2n+1}2^{2n+1-k}(k-n)\binom{k}n\\ &=\sum_{k=1}^{n+1}2^{n+1-k}k\binom{n+k}n\\ &=\sum_{k=1}^{n+1}2^{n+1-k}(n+k)\binom{n+k-1}{k-1}\\ &=\sum_{k=0}^n2^{n-k}(n+1+k)\binom{n+k}k\\ &=\sum_{k=0}^n2^{n-k}(n+1)\binom{n+1+k}k\\ &=(n+1)\sum_{k=0}^n2^{n-k}\binom{n+1+k}k\;. \end{align*}$$

Thus, we’d like to show that $$\sum_{k=0}^n2^{n-k}\binom{n+1+k}k=2^{2n+1}-\binom{2n+1}{n+1}\;.\tag{1}$$

Let $$s_n=\sum_{k=0}^n2^{n-k}\binom{n+1+k}k\;.$$ Then

$$\begin{align*}s_{n+1}&=\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+2+k}k\\ &=\sum_{k=0}^{n+1}2^{n+1-k}\left(\binom{n+1+k}k+\binom{n+1+k}{k-1}\right)\\ &=2\sum_{k=0}^n2^{n-k}\binom{n+1+k}k+\binom{2n+2}{n+1}+\sum_{k=0}^n2^{n-k}\binom{n+2+k}k\\ &=2s_n+\binom{2n+2}{n+1}+\frac12\left(s_{n+1}-\binom{2n+3}{n+1}\right)\;, \end{align*}$$

so $$s_{n+1}=4s_n+2\binom{2n+2}{n+1}-\binom{2n+3}{n+1}\;.$$ Taking $(1)$ as induction hypothesis, we have

$$\begin{align*} s_{n+1}&=2^{2n+3}-4\binom{2n+1}{n+1}+2\binom{2n+2}{n+1}-\binom{2n+3}{n+1}\\ &=2^{2n+3}-\binom{2n+3}{n+2}+2\left(\binom{2n+1}{n+1}+\binom{2n+1}n\right)-4\binom{2n+1}{n+1}\\ &=2^{2n+3}-\binom{2n+3}{n+2}+2\left(\binom{2n+1}{n+1}+\binom{2n+1}{n+1}\right)-4\binom{2n+1}{n+1}\\ &=2^{2n+3}-\binom{2n+3}{n+2}\;, &= \end{align*}$$

as desired.

Answer 3

I wrote down the generating fctn, $P_n(z) = \sum a_{n,j}z^j $ where the $a_{n,j}$ are the numbers in the table and I think they satisfy $P_n = \sum^n z^i + \frac {z+1}2 P_{n-1}$. This can be solved really pretty explicitly by dividing by $(\frac {z+1}2)^n$ and getting to a collapsing sum, but I lack the heart to do it, and couldn't swear you get anything useful.