How much weight is on each person in a human pyramid?

Question

After participating in a human pyramid and learning that it's very uncomfortable to have a lot of weight on your back, I figured I'd try to write out a recurrence relation for the total amount of weight on each person in the pyramid so that I could see just how much weight I ended up carrying.

There are many different kinds of human pyramids, but the sort of pyramid I'm referring to is one that looks like this:

               *
              / \
             *   *
            / \ / \
           *   *   *
          / \ / \ / \
         *   *   *   *
               ...

Here, each star is a person and the lines represent how each person is supported.

I'm going to make the unrealistic assumption that each person weighs the same amount, which I'll call $W$. I'm also going to assume that each person evenly transmits their weight (plus the total weight on top of them) to the two people below them.

Given these assumptions, I came up with a recurrence $w_{i, j}$ that says how much weight the $i$th person in row $j$ of the human pyramid carries on their back. It ended up coming out like this:

• $w_{1, 1} = 0$. The top person in the pyramid has no weight on them.
• $w_{1, n+1} = \frac{w_{1, n} + W}{2}$ The very first person on each row is shouldering half the weight of the person above them. That weight is given by the weight of the person ($W$) plus the load that person carries ($w_{1, n}$).
• $w_{n+1, n+1} = \frac{w_{n, n} + W}{2}$. The last person on each row shoulders half of the weight of the person above them.
• $w_{k+1, n+1} = \frac{w_{k+1, n} + w_{k, n} + 2W}{2}$. Each person on a row other than the first or the last shoulders half the weight from each of the people above them. The two people above them have $w_{k+1, n}$ and $w_{k, n}$ weight on them, and each one independently weighs $W$. Half of each of these weights is transmitted to the person below.

I was able to write a computer program that evaluated this recurrence and I was able to get values from it, but I have no idea how to find a closed-form expression for this recurrence. It's somewhat similar to the recurrence for combinations - each term is expressed as a sum of the two terms above it - but there's some extra junk thrown in as well.

Is there a standard approach for simplifying recurrences like this?

Thanks!

Answer 1

For a generating function approach, Let the coefficient of $x^k$ in $P_n(x)$ be the weight on the shoulders of person $k$ (starting at $k=0$ on the left) in row $n$ (starting at $n=0$ at the top). To compute $P_n(x)$ from $P_{n-1}(x)$, we first add the weight of the people in row $n-1$ to the weights on their shoulders: $$ P_{n-1}(x)+\frac{1-x^n}{1-x}\tag{1} $$ Those people distribute half their weight to each person below them, so we get $$ P_n(x)=\frac{1+x}2\left(P_{n-1}(x)+\frac{1-x^n}{1-x}\right)\tag{2} $$ Solving this recurrence yields $$ P_n(x)=\frac{1+x}{(1-x)^2}\left(1-2\left(\frac{1+x}{2}\right)^{n+1}+x^{n+1}\right)\tag{3} $$ $(3)$ can be checked by noting that $P_0(x)=0$ and then by checking that $(3)$ satisfies $(2)$.

Using the binomial theorem to multiply the terms in $(3)$, we get that $w_{m+1,n+1}$, the coefficient of $x^m$ in $P_n(x)$, is given by $$ 2m+1-\frac1{2^n}\sum_{k=0}^m(k+1)\binom{n+2}{m-k}\tag{4} $$ There might be some special function of which I am unaware (a hypergeometric function perhaps), but in terms of common functions, $(4)$ is as close to a closed form as I think there is.

---

Solving the recurrence

Let $Q_n(x)=\left(\frac2{1+x}\right)^nP_n(x)$, then multiplying $(2)$ by $\left(\frac2{1+x}\right)^n$ yields $$ \begin{align} Q_n(x) &=Q_{n-1}(x)+\frac{1-x^n}{1-x}\left(\frac2{1+x}\right)^{n-1}\\ &=Q_{n-1}(x)+\frac12\frac{1+x}{1-x}\left(1-x^n\right)\left(\frac2{1+x}\right)^n\\ &=Q_{n-1}(x)+\frac12\frac{1+x}{1-x}\left(\left(\frac2{1+x}\right)^n-\left(\frac{2x}{1+x}\right)^n\right)\tag{5} \end{align} $$ Summing the geometric series gets a bit messy, $$ \begin{align} Q_n(x) &=\frac12\frac{1+x}{1-x}\sum_{k=1}^n\left(\left(\frac2{1+x}\right)^k-\left(\frac{2x}{1+x}\right)^k\right)\\ &=\frac12\frac{1+x}{1-x}\left(\frac2{1+x}\frac{\left(\frac2{1+x}\right)^n-1}{\frac2{1+x}-1}-\frac{2x}{1+x}\frac{\left(\frac{2x}{1+x}\right)^n-1}{\frac{2x}{1+x}-1}\right)\\ &=\frac{1+x}{1-x}\left(\frac{\left(\frac2{1+x}\right)^n-1}{1-x}+x\frac{\left(\frac{2x}{1+x}\right)^n-1}{1-x}\right)\\ &=\frac{1+x}{(1-x)^2}\left(\left(\frac2{1+x}\right)^n-1+x\left(\frac{2x}{1+x}\right)^n-x\right)\\ &=\frac{1+x}{(1-x)^2}\left(\left(\frac2{1+x}\right)^n\left(1+x^{n+1}\right)-(1+x)\right)\tag{6} \end{align} $$ Multiplying by $\left(\frac{1+x}2\right)^n$, we arrive at $(3)$: $$ P_n(x)=\frac{1+x}{(1-x)^2}\left(1+x^{n+1}-2\left(\frac{1+x}2\right)^{n+1}\right)\tag{7} $$

---

Examples: $$ \begin{align} P_0(x)&=0\\ P_1(x)&=\frac12+\frac12x\\ P_2(x)&=\frac34+\frac32x+\frac34x^2\\ P_3(x)&=\frac78+\frac{17}{8}x+\frac{17}{8}x^2+\frac78x^3\\ P_4(x)&=\frac{15}{16}+\frac52x+\frac{25}{8}x^2+\frac52x^3+\frac{15}{16}x^4 \end{align} $$ The bottom-middle person on a $5$-tier pyramid is supporting more than $3$ people's weight on their back.

Answer 2

\begin{align} \Psi_{n}\left(x\right) &\equiv \sum_{k = 1}^{\infty}\phi_{k,n}\,x^{k} = \sum_{k = 1}^{\infty}x^{k} \left(2\phi_{k\ +\ 1,n\ +\ 1} - \phi_{k\ +\ 1,n} - 2\right) = 2\sum_{k = 2}^{\infty}x^{k\ -\ 1}\,\phi_{k,n\ +\ 1} \\[3mm]&- \sum_{k = 2}^{\infty}x^{k\ -\ 1}\phi_{k,n} - 2\,{x \over 1 - x} = 2\left\lbrack{1 \over x}\,\Psi_{n\ +\ 1}\left(x\right) - \phi_{1,n\ +\ 1}\right\rbrack - \left\lbrack% {1 \over x}\,\Psi_{n}\left(x\right) - \phi_{1,n} \right\rbrack \\[3mm]&- 2\,{x \over 1 - x} \end{align}

\begin{align} -----&------------------------------------ \end{align}

$$ 2\Psi_{n\ +\ 1}\left(x\right) - \left(1 + x\right)\Psi_{n}\left(x\right) = x\left(2\phi_{1,n\ +\ 1} - \phi_{1,n}\right) + {2x^{2} \over 1 - x} = x + {2x^{2} \over 1 - x} = {x + x^{2} \over 1 - x} $$

\begin{align} -----&------------------------------------ \end{align}

$$ \Psi_{n\ +\ 1}\left(x\right) - {x + x^{2} \over \left(1 - x\right)^{2}} = {1 \over 2}\left(1 + x\right) \left\lbrack% \Psi_{n}\left(x\right) - {x + x^{2} \over \left(1 - x\right)^{2}} \right\rbrack $$

\begin{align} -----&------------------------------------ \end{align}

$$ \Psi_{n\ +\ 1}\left(x\right) = {x + x^{2} \over \left(1 - x\right)^{2}} + {1 \over 2^{n}}\left(1 + x\right)^{n}\,\Psi_{1}\left(x\right) $$ \begin{align} -----&------------------------------------ \end{align}

Multiply by $y^{n}$ and perform the sum for $n \geq 1$. With $\Psi\left(x,y\right) \equiv \sum_{n = 1}^{\infty}\sum_{k = 1}^{\infty}\phi_{k,n}\,x^{k}y^{n}$:

$$ \Psi\left(x,y\right) = {x + x^{2} \over \left(1 - x\right)^{2}}\,{y^{2} \over 1 - y} + {y \over 1 - \left(x + 1\right)y/2}\,\Psi_{1}\left(x\right) $$

That determines $\phi_{k,n}$ in terms of $\phi_{k,1}$. It yields an equation for $\phi_{k,1}$. It's done.

Answer 3

Let's have $W=1$.

If $n$ is number of row (starting with $0$) and $k$ is number of human (starting with $0$ from the left side), then $$w_{k,n}=n+1-\frac{\binom{n}{k}+2S_{k,n}}{2^n}$$

Where $$S_{k,n}=\sum_{0\leq i\leq n}\binom{n}{i}\left|k-i\right|$$

I couldn't get closed form for $S_{k,n}$, but I have recurrence $S_{k,0}=\left|k\right|$ and $S_{k,n}=S_{k-1,n-1}+S_{k,n-1}$.

---

$m_{k,n}$ will be "total" weight of the human (his mass and all mass he gets from higher levels of pyramid).

So $m_{0,0}=1$. And, to make anything easier I will introduce imaginary humans outside of the pyramid: $m_{k,0}=2-2\left|k\right|- \left[k=0\right]$. ($[k=0]$ is $1$ if $k=0$ else it's $0$).

Then $$m_{k,n}=\frac{m_{k-1,n-1}+m_{k,n-1}}{2}+1$$ and for $0\leq k\leq n$ (for real humans) everything is okay.

If $t_{k,n}=m_{k,n}-n$ then $m_{k,n}=t_{k,n}+n$ and $t_{k,n}=\frac{t_{k-1,n-1}+t_{k,n-1}}{2}$ (with $t_{k,0}=m_{k,0}$).

Let's also have $u_{k,n}=2^nt_{k,n}$. Then $t_{k,n}=\frac{u_{k,n}}{2^n}$ and $u_{k,n}=u_{k-1,n-1}+u_{k,n-1}$ (with $u_{k,n}=t_{k,0}=m_{k,0}$).

If we get formula for $u_{k,n}$, then $m_{k,n}=t_{k,n}+n=\frac{u_{k,n}}{2^n}+n$

Now I use formula $$u_{k,n}=\sum_i \binom{n}{i} u_{k-i,0}$$ $$u_{k,n}=\sum_i \binom{n}{i} \left(2-2\left|k-i\right|- \left[k-i=0\right]\right)=\\ =2\sum_i \binom{n}{i}-2\sum_i \binom{n}{i} \left|k-i\right|- \sum_i \binom{n}{i}\left[k-i=0\right]=\\ =2^{n+1}-2\sum_i \binom{n}{i} \left|k-i\right|-\binom{n}{k}$$ $$m_{k,n}=\frac{2^{n+1}-2\sum_i \binom{n}{i} \left|k-i\right|-\binom{n}{k}}{2^n}+n=\\ =n+2-\frac{\binom{n}{k}+2\sum_i \binom{n}{i} \left|k-i\right|}{2^n}$$

And $w_{k,n}=m_{k,n}-1$.

Answer 4

Setup and change of indices

Put $W=1$. Also change the indices of $w_{i,j}$ so that $(i,j)$ points relatively to the top person at (0,0) by moving $i$ persons down-right and then $j$ persons down-left. So (i,j) points to the $i$'th person in the $(i+j)$'th row counting from zero.

The weight distribution of each person

Let us first consider how the top persons weight is distributed down through the pyramid. Then we have the recurrence $$ w_{i,j}=\frac{w_{i-1,j}+w_{i,j-1}}{2} $$ where $w_{0,0}=1$ and $w_{i,j}=0$ outside of the pyramid (that is $i<0$ or $j<0$). This can easily be solved to get $w_{i,j}=\frac{1}{2^{i+j}}\binom{i+j}{i}$. So this is just a variation over Pascal's Triangle where the $n$'th row is divided by $\frac{1}{2^n}$. Let VPT denote this Variation over Pascal's Triangle.

Now move on to consider how the weight of the person at position $(i,j)$ is distributed. The pattern is basically the same! Isolating each person like this, we can see how the distibution of a single persons weight forms a copy of VPT having its top corner at $(i,j)$.

Analysis of the general case

Consider the person at $(i,j)$. This person is included in all VPT's with top corners in $P=\{0,...,i\}\times\{0,...,j\}$ and carries the weight distributed according to all these VPT's. Only we have added 1 too much since the person is included as top corner in its own VPT but does not carry its own weight in the scope of this question.

Now consider $(s,t)\in P$ as one such top corner. Then the position of $(i,j)$ relative to this will be $(x,y)=(i-s,j-t)\in P$. Note here how the map $(s,t)\mapsto (i-s,j-t)$ maps $P$ to itself bijectively. Given this observation one may deduce that the distributed weight contributions form a sum that can be expressed as: $$ w_{i,j}+1=\sum_{x=0}^i\sum_{y=0}^j\frac{1}{2^{x+y}}\binom{x+y}{x} $$ Though not closed form, I believe this to be a very nice and symmetric expression for $w_{i,j}$. Still, I consider the answer given by robjohn just brilliant. BTW my formula yields the same values as robjohn got, and the next example of his should read:

Example (continued from robjohn)

$P_n(x)=\tfrac{31}{32}+\tfrac{87}{32}x+\tfrac{61}{16}x^2+\tfrac{61}{16}x^3+\tfrac{87}{32}x^4+\tfrac{31}{32}x^5$

Also note that the sum of coefficeints of each row in the pyramid should be a triangular number since the persons in the $n$'th row carries the weight of $T_n$ people (the $n$'th triangular number).

Answer 5

(I've deleted the previous answer which was wrong.)

Now I have, without proof, by heuristics a direct formula for the entries in the weight matrix if we consider its entries as $$ W=\small \begin{bmatrix} 0 & . & . & . & . & . \\ 1/2 & 1/2 & . & . & . & . \\ 3/4 & 3/2 & 3/4 & . & . & . \\ 7/8 & 17/8 & 17/8 & 7/8 & . & . \\ 15/16 & 5/2 & 25/8 & 5/2 & 15/16 & . \\ 31/32 & 87/32 & 61/16 & 61/16 & 87/32 & 31/32 \end{bmatrix}$$ as it was also shown by Rob Johnson.

It was easier to find the recurrences and then the direct formula when I included the unit-weight per person, such that I have: $$ X= \small \begin{bmatrix} 1 & . & . & . & . & . \\ 3/2 & 3/2 & . & . & . & . \\ 7/4 & 5/2 & 7/4 & . & . & . \\ 15/8 & 25/8 & 25/8 & 15/8 & . & . \\ 31/16 & 7/2 & 33/8 & 7/2 & 31/16 & . \\ 63/32 & 119/32 & 77/16 & 77/16 & 119/32 & 63/32 \end{bmatrix} $$ or, expanded to make it better visible, rowscaled by powers of 2: $$ Y =\small \begin{bmatrix} 1 & . & . & . & . & . \\ 3 & 3 & . & . & . & . \\ 7 & 10 & 7 & . & . & . \\ 15 & 25 & 25 & 15 & . & . \\ 31 & 56 & 66 & 56 & 31 & . \\ 63 & 119 & 154 & 154 & 119 & 63 \end{bmatrix} $$

Let $r$ denote the rowindex, $c$ denote the column-index, both beginning at zero, $c \le r$ then we have $$ w_{r,c} = 1+2c - {\sum_{k=0}^c \binom{r+2}{k}\cdot(1+c-k)\over 2^r}$$

In terms of the $X$-matrix this was: $$ x_{r,c} = 2\cdot(1+c) - {\sum_{k=0}^c \binom{r+2}{k}\cdot(1+c-k)\over 2^r}$$ and in terms of the $Y$-matrix this was $$ y_{r,c} = 2^{r+1}\cdot(1+c) - \sum_{k=0}^c \binom{r+2}{k}\cdot(1+c-k)$$

---

[added] I found it interesting to consider a more general aspect. The idea is to assume an infinitely wide pyramid of "zero-humans" or "ghosts" which have weight $o$ (which for the final evaluation is then to set to zero). This is the infinitely wide grey shaded area in the following picture. The structure for this area is very simple and homogenuous: in each row $r$ the weight in one entry is $r \cdot o$.
Now one of the top-most ghosts "gets a soul", becomes human and thus gravitation gives him a pressing weight "w". All ghosts which are touched by his feet become then human too, and their weight changes to "w" as well, and this iterates downwards.

The picture shows, how this distributes to the bottom:

Note, how the coefficients at a w and at the o in the same cell add to make the equilibrium-coefficient of the same row, if we would set $w=o$.

It is in general the description of a certain disturbance inserted into a equilibrium, and I'm curious, whether this can even be made continuous (like the generalization of the binomial-coefficients using the Gamma-function)

---

[added2] With iterations of this type it is often useful to express the problem in a matrix-notation and convert iteration into matrix-powers. Then sometimes one can find a closed form in terms of fixed matrices and the iteration-parameter is then only in the exponent of a matrix. (Clearly that does not finally solve the problem of the finite sums, sometimes recursive, in the original, non-matrix, representation but moves it into the internal dotproducts for the matrix-powers. But for the reader of the formula this might be convenient).

First let's define a rowvector $U=[1,0,0,...]$ of some dimension n which represents the weight of the person on the top where n is the final width of the pyramide.

Then one iteration should have the effect, that $U_0$ changes to $V_1=[1/2,1/2,0,0,...]$ which is the received weight for the lower layer and then $U_1$ must also have the unit-weights for the persons to become $U_1=[3/2,3/2,0,0,0...]$ .

A matrix, which performs $U_0 \to V_1$ is $M= \frac12 \small\begin{bmatrix}1&1&0&0&0&0&...\\0&1&1&0&0&0&...\\0&0&1&1&0&0&... \\ \vdots & & & & & &\ddots \end{bmatrix}$ such that $$U_0 \cdot M = V_1 = \left[ \frac 12,\frac12, 0,0,0,... \right] $$.
After that we need a matrix, which transfers two ones for the unit weights into $V_1$ and we can do this simply by addition of the unscaled $M$ such that $$ U_0 \cdot 2M = [1,1,0,0,...]$$ and we have $$ U_0 \cdot M + U_0 \cdot 2M = U_1 = [3/2,3/2,0,0,...]$$

But now, if the number of persons increase by the iterations, the second summand is not sufficient; we need so many unit-weigths as we have persons in one iteration. So we need to find a matrix, whose k't power gives k leading ones in the top row. A simple candidate is the matrix of the upper unit-subdiagonal, let's call it $L$: $$ L = \small \begin{bmatrix}0&1&0&0&0&0&...\\0&0&1&0&0&0&...\\0&0&0&1&0&0&... \\ \vdots & & & & & &\ddots \end{bmatrix} $$ Then the k'th power of shifts the diagonal to the right to the k'th position, and the sum of $L^0 + L^1 + L^2 + ... + L^K$ gives $k+1$ ones. Then for the first iteration we can write $$ U_0 \cdot M + U_0 \cdot (L^0 + L^1) = U_1 $$ or $$ U_0 \cdot (M + (L^0 + L^1)) = U_1 $$

We can then simply proceed by $$ U_1 \cdot (M + (L^0 + L^1 + L^2)) = U_2 $$ which is also $$ U_0 \cdot (M^2 + (L^0 + L^1)M+ (L^0 + L^1 + L^2)) = U_2 $$ and it is obvious how this iterates.

But we see now, that we have partial geometric series depending on the iteration-parameter, and they have a closed form, namely the cyclotomic polynomial of the k'th order.
For the cyclotomic polynomial we need to write $$ L^0+L^1+... + L^k = (I - L^{k+1}) \cdot (I - L)^{-1} $$ Let's denote that inverse as $R$ . We find that it is just the upper triangular unit-matrix (as expected by the series representation!) $$R = \small \begin{bmatrix}1&1&1&1&1&1&...\\0&1&1&1&1&1&...\\0&0&1&1&1&1&... \\ \vdots & & & & & &\ddots \end{bmatrix} $$ Then we have $$ U_0 \cdot ((I-L^1)R M^k + (I-L^2)R M^{k-1}+ (I-L^3)R M^{k-2} +...+(I-L^{k+1})R) = U_k $$ (where I smoothed the formula at the leading $M^k$

Because it is also $M=I + L$ the matrices $M$ and $L$ and $R$ commute all and we can rotate the coefficients for any convenience. We can isolate a geometric sum of powers of $M$:

$$ U_0 \cdot ( R( M^k + M^{k-1}+ M^{k-2} +...I) \\ -R(L^1 M^k + L^2 M^{k-1}+ L^3 M^{k-2} +...+L^{k+1})) = U_k $$ Now the powers of $M$ are also partial geometric series, and we need the reciprocal, let's denote it as $S$: $$ S= (I - M)^-1 =\small \begin{matrix} 2&2&2&... \\ 0&2&2& ...\\ 0&0&2&...\\ ... \end{matrix}$$ which happens to be just $S=2R$ and is also commuting with every matrix in the game so far.

Then we have $$ U_0 \cdot \left( R( I - M^{k+1})S \\ -R(L^1 M^k + L^2 M^{k-1}+ L^3 M^{k-2} +...+L^{k+1}) \right) = U_k \\ $$
and the last parenthese of variable length can be reduced similarly because $M$ is invertible and with a matrix $W=L \cdot M^{-1}$ and $T=(I -W)^{-1} $we have $$ U_0 \cdot \left( R( I - M^{k+1})S -R L M^k (I + W+ W^2 +...+W^k) \right) \\ = U_0 \cdot \left( R( I - M^{k+1})S -R L M^k (I -W^{k+1}) T) \right) \\ \qquad \qquad = U_k \\ $$

This formula has a fixed length for any iteration parameter. Only the variable matrix powers contain that parameter. (Possibly from this one can invent fractional iterates, but that's not the focus here...)