Prove by induction that $(x+1)^n - nx - 1$ is divisible by $x^2$

Question

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.

Answer 1

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$$

Answer 2

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$.

Answer 3

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.

Answer 4

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.

Answer 5

The induction step is arithmetically clearer if done $\!\bmod \color{#c00}{ x^2},\,$ i.e. using modular arithmetic, i.e. using $\,\rm\color{#0a0}{CPR} =$ Congruence Product Rule), and induction hypothesis $P(n)$ 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, i.e. the inductive step of incrementing $\,n\,$ amounts to scaling the induction hypothesis congruence by $1+x$ then reducing that $\!\bmod {\color{#c00}{x^2}}.\,$ This arithmetic would be obfuscated if done instead using divisibility relations (vs. above (congruence) equations). This highlights the power of modular 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).

The same proof works for $\,(a+x)^n,\,$ i.e.

$$\begin{align}{\rm mod}\,\ \color{#e00}{x^2}:\,\ (a+ x)^n\, \ \ \equiv&\,\ \ a^n + \color{#0af}n\:\!a^{\color{#0af}{n-1}}x\qquad\qquad\ \ \ \ {\rm i.e.}\ \ P(\color{#0af}n) \\[2pt] {\rm\color{#0a0}{CPR}}\Longrightarrow\ \ (a+x)^{\color{}{n+1}}\! \equiv &\:\!\ (a^n+na^{n-1}x)(a + x)\quad\,\ \text{by $\,a\!+\!x\,$ times prior}\\[2pt] \equiv &\,\ \ a^{n+1}+ na^nx+a^nx+na^{n-1}\color{#e00}{x^2}\\[2pt] \equiv &\,\ \ a^{n+1}\!+\! (\color{#0af}{n\!+\!1})a^{\color{#0af}n}x\qquad\ \ \ \ \ {\rm i.e.}\ \ P(\color{}{\color{#0af}{n\!+\!1}})\\[2pt] \end{align}\qquad\qquad$$

Generalization $ $ Using the above idea it is easy to generalize, e.g. from this answer

$\!\begin{align}\rm{\bf Theorem}\ \ \forall n\in\Bbb N\!:\ d\mid f(n) = a^n\! + b\:\!n + c &\rm \iff d\mid \color{blue}{(a\!-\!1)^2},\, \color{brown}{a\!+\!b\!-\!1},\, \color{darkorange}{1\!+\!c}\\ &\rm \iff d\mid f(0),\,f(1),\,f(2)\end{align}$