# 证明和问题的解决 Proofs and Problem Solving MATH08059

0

Proof 1. the number of lattice paths reaching $(k, n-k)$ is $\left(\begin{array}{l}n \ k\end{array}\right)$. Each path arrives at $(k, n-k)$ from exactly one of the points $(k, n-k-1)$ and $(k-1, n-k)$. By Proposition $5.21$ again, there are $\left(\begin{array}{c}n-1 \ k\end{array}\right)$ paths of the first type and $\left(\begin{array}{c}n-1 \ k-1\end{array}\right)$ paths of the second type.

Proof 2 . Using the subset model, we count the $k$-sets in [ $n$ ]. There are $\left(\begin{array}{c}n-1 \ k\end{array}\right)$ such sets not containing $n$ and $\left(\begin{array}{c}n-1 \ k-1\end{array}\right)$ such sets containing $n$.

Proof 3. $(1+x)^{n}=(1+x)(1+x)^{n-1}$. Using the Binomial Theorem, we expand both $(1+x)^{n}$ and $(1+x)^{n-1}$ to obtain

$$\sum_{k=0}^{n}\left(\begin{array}{l} n \ k \end{array}\right) x^{k}=(1+x) \sum_{k=0}^{n-1}\left(\begin{array}{c} n-1 \ k \end{array}\right) x^{k}=\sum_{k=0}^{n-1}\left(\begin{array}{c} n-1 \ k \end{array}\right) x^{k}+\sum_{k=0}^{n-1}\left(\begin{array}{c} n-1 \ k \end{array}\right) x^{k+1}$$
Shifting the index in the last summation yields $\sum_{k=1}^{n}\left(\begin{array}{c}n-1 \ k-1\end{array}\right) x^{k}$. Since $\left(\begin{array}{c}n-1 \ n\end{array}\right)=$ $\left(\begin{array}{c}n-1 \ -1\end{array}\right)=0$, we can add $\left(\begin{array}{c}n-1 \ n\end{array}\right)$ to the first sum and $\left(\begin{array}{c}n-1 \ -1\end{array}\right)$ to the second to obtain
$$\sum_{k=0}^{n}\left(\begin{array}{l} n \ k \end{array}\right) x^{k}=\sum_{k=0}^{n}\left[\left(\begin{array}{c} n-1 \ k \end{array}\right)+\left(\begin{array}{l} n-1 \ k-1 \end{array}\right)\right] x^{k}$$

## MATH08059COURSE NOTES ：

there is a polynomial $g$ such that
$$k !\left(\begin{array}{l} i \ k \end{array}\right)=i(i-1) \cdots(i-k+1)=i^{k}-\left(\begin{array}{c} k \ 2 \end{array}\right) i^{k-1}+g(i),$$
with $g$ of degree at most $k-2$. Solving for $i^{k}$ yields $i^{k}=k !\left(\begin{array}{l}i \ k\end{array}\right)+\left(\begin{array}{l}k \ 2\end{array}\right) i^{k-1}-g(i)$.
We use induction on $k$. For $k=1$, the formula $\sum_{i=1}^{n} i=\frac{1}{2} n^{2}+\frac{1}{2} n$ agrees with the claim. For $k>1$, we have
$$\sum_{i=1}^{n} i^{k}=k ! \sum_{i=1}^{n}\left(\begin{array}{l} i \ k \end{array}\right)+\left(\begin{array}{c} k \ 2 \end{array}\right) \sum_{i=1}^{n} i^{k-1}-\sum_{i=1}^{n} g(i)$$