The given triangular number table is as follows: Among them, the numbers in the first row are $1, 2, 3, ..., 98, 99, 100$. Starting from the second row, each number is equal to the sum of the left and right numbers in the row above it. Find the value of $M$.
Problem
Source: China Northern MO 2008 p2 CNMO
Tags: Pascal's Triangle, algebra
aidan0626
04.05.2024 23:26
Let $a_n$ be the answer for a triangle with $n$ numbers. Then, we can get that $a_n=2a_{n-1}+2^{n-2}$ by noting that the differences between numbers in the $n$th row is $2^n$ (top row is row 0) and looking at the left side of the triangle. We can then inductively proof that $a_n=2^{n-1}+(n-1)2^{n-2}$, so the answer is $2^{99}+99\cdot2^{98}.$
AshAuktober
14.10.2024 17:01
Note that we can rewrite the number of times each initial number $n$ shows up in the summation for $M$ as the number of lattice paths to $M$ from the number, which comes out to be $\binom{99}{n-1}$. So we have
$$M = \sum_{n = 1}^{\infty} n\binom{99}{n-1} = \sum_{k = 0}^{\infty} (k+1)\binom{99}{k}$$$$ = 2^{99} + \sum_{k \ge 0} k \binom{99}{k}.$$But the latter part can be easily computed by considering the derivative of the generating function of $(1+x)^{99}$, which turns out to be $99(1+x)^{98}$; in fact, it is precisely this generating function evaluated at $x = 1$. So the final answer is $\boxed{2^{99} + 99 \cdot 2^{98}}$.