# Proof- central term of recursive pyramid

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.

-
This question is closely related. The numerators in the triangle are OEIS A157933, the central numerators are OEIS A033504, and the central fractions give the expected number of tosses of a coin required to obtain $n$ heads or $n$ tails. –  Brian M. Scott Apr 1 '12 at 21:39
How does the expected number of tosses formulate? –  Ali Apr 1 '12 at 22:08
I’ve not really thought about it yet; that information was simply lifted from the OEIS entry. –  Brian M. Scott Apr 1 '12 at 22:09
However, I think that it’s off by one: that should be the expected nr. of tosses required to get $n+1$ heads or $n+1$ tails. E.g., if you toss a fair coin twice, the probability that you have two H or two T is $1/2$, and if you don’t yet have two the same, you’re certain to get a match on the third toss, so the expected nr. of tosses for two H or two T is $\frac12\cdot 2+\frac12\cdot 3=\frac52$. –  Brian M. Scott Apr 1 '12 at 22:17
You would probably need to find a formula for all the entries in the triangle, not just the central ones, if you wanted to prove it by induction. –  Greg Martin Apr 1 '12 at 22:29

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

-
I was able to use another intuitive approach grouping terms in the pyramid and likening them to pascal's triangle to come up with a summation notation formula. Can we make a generalization, by any chance, about any term in the pyramid, using 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. –  Ali Apr 12 '12 at 13:51
@Joriki- please see the comment above. –  Ali Apr 12 '12 at 16:02
You have received the bounty. Thank you for the well written solution! –  Ali Apr 13 '12 at 1:13

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.

-

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.

-