Inductive proofs

Inductive proofs are fun. Binomial coefficients These series identities are based on exercises from the first chapter of Statistical Inference1 Alternating sum For n≥2, ∑k=0n(−1)k(nk)=0 For n=2, ∑k=02(−1)k(2k)=1−2+1=0. Induction hypothesis (IH): assume that this holds for n≥2. We want to show that ∑k=0n+1(−1)k(nk)=0 follows. Use Pascal's rule: (nk)=n!k!(n−k)!(1)=(n−1)!(k+n−k)k!(n−k!)(2)=(n−1)!(kk!(n−k)!+n−kk!(n−k)!)(3)=(n−1)!(k−1)!(n−1−k+1)!+(n−1)!k!(n−1−k)!(4)=(n−1k−1)+(n−1k)(5) Write (nk) as ak. Then, ∑k=0n+1(−1)k(n+1k)(1)=1+∑k=1n(−1)k((nk−1)+(nk))+(−1)n+1·1(2)=1+∑k=1n(−1)kak+∑k=1n(−1)kak−1+(−1)n+1·1(3)=∑k=0n(−1)kak+∑k=1n(−1)kak−1+(−1)n+1·an(4)=0−∑k=0n−1(−1)kak−(−1)n·an(5)=−(∑k=0n−1(−1)kak+(−1)n·an)(6)=−(∑k=0n(−1)kak)(7)=0(8) Casella, G., & Berger, R. L. (2002). Probability Theory. Statistical inference (2nd ed.). Cengage. ↩