Prove by induction that $(x+1)^n - nx - 1$ is divisible by $x^2$ Prove by induction that $(x+1)^n - nx - 1$ is divisible by $x^2$
Basis step has already been completed. I've started off with the inductive step as just $n=k+1$, trying to involve $f(k)$ into it so that the left over parts can be deducible to be divisible by $x^2$ but getting stuck on this inductive step.
 A: By the Binomial theorem, $(x+1)^n$ ends in $nx+1$, so that the remaining terms are multiples of $x^2$.

By induction, $(x+1)^n$ ends in $nx+1$. This is true for $n=1$, $(x+1)^1$ ends in $x+1$.
Now assume that $(x+1)^n$ ends in $nx+1$. Multiplying by $x+1$, we get $nx+x+1$ and higher order terms, hence $(x+1)^{n+1}$ ends in $(n+1)x+1$.
A: Hint:
$$(x+1)^{n+1}-(n+1)x-1=(x+1)(x+1)^n-nx-x-1$$$$=(x+1)((x+1)^n-nx-1)+(nx+1)(x+1)-nx-x-1$$$$=(x+1)((x+1)^n-nx-1)+nx^2$$
A: Lets say the statement is true for $n=k$ i.e., $(1+x)^k-xk-1$ is divisible by $x^2$  (Lets say, $(1+x)^k-xk-1=mx^2$  )
To show $(1+x)^{k+1}-x(k+1)-1$ is divisble by $x^2$
$(1+x)^{k+1}-x(k+1)-1$
$=(1+x)^k(1+x)-xk-x-1$
$=(1+x)^k+x(1+x)^k-xk-x-1$
$=\{(1+x)^k-xk-1\}+x(1+x)^k-x$
$=mx^2+x \{(1+x)^k-1\}$ = 
$=mx^2+x \{(1+x)^k-1-xk+xk\}$
$=mx^2+x \{mx^2+xk\}$
$=mx^2+x .x\{mx+k\}$
$=x^2\{m+\{mx+k\}\}$
Hence it is divisible by $x^2$ and hence it finishes the induction.
A: The base case is trivial. Suppose the result holds for $k$; then
$$
(x+1)^k-kx-1=x^2f_k(x)
$$
for some polynomial $f_k$. Therefore $(x+1)^k=1+kx+x^2f_k(x)$ and
\begin{align}
(x+1)^{k+1}-(k+1)x-1
&=(x+1)(x+1)^k-kx-x-1\\[6px]
&=(x+1)(1+kx+x^2f_k(x))-kx-x-1\\[6px]
&=\color{red}{x}+kx^2+x^3f_k(x)+\color{red}{1}+\color{red}{kx}+
  x^2f_k(x)-\color{red}{kx}-\color{red}{x}-\color{red}{1}\\[6px]
&=x^2(k+xf_k(x)+f_k(x))
\end{align}
This, by the way, says that
$$
f_{k+1}(x)=k+(x+1)f_k(x)
$$
but it's irrelevant for the proof.
A: The induction step is arithmetically clearer if done $\!\bmod \color{#c00}{ x^2},\,$ i.e. using modular arithmetic (notably $\,\rm\color{#0a0}{CPR} =$ Congruence Product Rule) the induction step is
$$\!\begin{align}{\rm mod}\,\ \color{#e00}{x^2}:\,\  (1+ x)^n\, \ \  \equiv&\,\ \ 1 + \color{#0af}n\:\!x\qquad\qquad\ \ \ \  {\rm i.e.}\ \ P(\color{#0af}n)\\[1pt]
{\rm\color{#0a0}{CPR}}\Longrightarrow\ \ (1+x)^{\color{}{n+1}}\! \equiv &\:\!\  (1+nx)(1 + x)\quad\,\ \text{by $\,1\!+\!x\,$ times prior}\\[1pt] 
\equiv &\,\ \ 1+ nx+x+n\:\!\color{#e00}{x^2}\\[1pt] 
 \equiv &\,\ \ 1\!+\! (\color{#0af}{n\!+\!1})x\qquad\ \ \ \ \ {\rm i.e.}\ \ P(\color{}{\color{#0af}{n\!+\!1}})\\[2pt]  
  \end{align}\qquad\qquad$$
Remark $ $ Note how the use of modular arithmetic greatly clarifies the arithmetical essence of the matter (which is obfuscated when instead proved using divisibility relations). This highlights the power of mod arithmetic - to focus on the remainders (and ignore the unneeded quotients).
This first $2$ terms (order $2$) truncation of the Binomial Theorem often proves useful in number theory, e.g. see here (and compare to Bernoulli's inequality).
