1.25 Binomial by induction: induction step

Induction step: Assume the $P_{n}$ is true and consider $P_{n+1}$. We have

$$(1+X)^{n+1}=(1+X)(1+X)^{n}$$

$$=(1+X)\Bigl(1+{{n}\choose{1}}X+{{n}\choose{2}}X^{2}+\dots+{{n}\choose{n}}X^{n}\Bigr);$$

this is a sum of powers of $X$ from $1$ to $X^{n+1}$, and the coefficient of $X^{k+1}$ is

$${{n}\choose{k}}+{{n}\choose{k+1}}={{n+1}\choose{k+1}}$$

by the recurrence relation; so

$$(1+X)^{n+1}=1+{{n+1}\choose{1}}X+{{n+1}\choose{2}}X^{2}+\dots+{{n+1}\choose{n+1}}X^{n+1},$$

hence result by induction.