这是一份ed.ac.uk爱丁堡大学MATH08059作业代写的成功案例
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}
$$
MATH08059 COURSE 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)
$$