November 24, 2021 – Physicspupil

Prove by mathematical induction that $n(n^2+2)$ is divisible by $3$ for all positive integral values of $n$ .

Solution.

Let $P(n)$ be the statement that

$P(n):\enspace n(n^2+2)\textrm{ is divisible by }3\textrm{ for }n\in\mathbb{Z}^{+}$

First, we wish to show $P(1)$ holds true.

$\begin{aligned} &\quad (1)\big( (1)^2 + 2\big) \\ & = 1(1+2) \\ & = 3\qquad (\textrm{divisible by }3)\\ \end{aligned}$

$\therefore$ $P(1)$ is true.

Once we assume that $P(n)$ is true for some positive integral values, we wish to show $P(n+1)$ is true.

$\begin{aligned} &\quad (n+1)\big( (n+1)^2 + 2\big) \\ & = (n+1)(n^2+2n+3) \\ & = n^3 + 3n^2 + 5n +3 \\ \end{aligned}$

Let $f(x)=x^3+3x^2+5x+3$ .

Suppose we can divide $f(x)$ by $3$ , i.e.,

$f(x)=3\cdot g(x)$

for some $g(x)=Ax^3+Bx^2+Cx+D$ where $A,B,C,D\in\mathbb{R}$ .

Then, let’s see

$\begin{aligned} \frac{f(x)}{g(x)} & = 3 \\ \frac{\mathrm{d}}{\mathrm{d}x}\bigg( \frac{f(x)}{g(x)}\bigg) & = \frac{\mathrm{d}}{\mathrm{d}x}(3) \\ \frac{g(x)f'(x)-f(x)g'(x)}{[g(x)]^2} & = 0 \\ g(x)f'(x)-f(x)g'(x) & = 0 \\ \end{aligned}$

Plugging in $f(x)$ , $f'(x)$ , $g(x)$ , and $g'(x)$ , we have

$\begin{aligned} &\quad (Ax^3+Bx^2+Cx+D)(3x^2+6x+5) \\ & = (x^3+3x^2+5x+3)(3Ax^2+2Bx+C) \\ \end{aligned}$

$\begin{aligned} &\quad \enspace \textrm{LHS} \\ & = (3A)x^5 + (6A+3B)x^4 + (5A+6B+3C)x^3 \\ &\qquad\quad + (5B+6C+3D)x^2 + (5C+6D)x + (5D) \\ \end{aligned}$

$\begin{aligned} &\quad \enspace \textrm{RHS} \\ & = (3A)x^5 + (9A+2B)x^4 + (15A+6B+C)x^3 \\ &\qquad\quad + (9A+10B+3C)x^2 + (6B+5C)x + (3C) \\ \end{aligned}$

We have a set of five equations below:

$\begin{aligned} 6A + 3B & = 9A + 2B \\ 5A+6B+3C & = 15A+6B+C \\ 5B+6C+3D & = 9A+10B+3C \\ 5C +6D & = 6B+5C \\ 5D & = 3C \\ \end{aligned}$

which can be summarized to

$\displaystyle{A=\frac{B}{3}=\frac{C}{5}=\frac{D}{3}}$ ,

that is equivalent to saying

$g(x)=\displaystyle{\frac{f(x)}{3}=\frac{x^3}{3}+x^2+\frac{5x}{3}+1}$ ,

viz. I have been wasting time over a circular reasoning of no use.

I should have tried to attest otherwise that $g(x)$ is of some positive integral values, even though this is $\textrm{\scriptsize{NOT}}$ proving the statement $P(n)$ by mathematical induction firsthand.

Reformulation.

To show that the following statement $Q(x)$ holds true:

$Q(x):\quad \displaystyle{\frac{x^3}{3}+x^2+\frac{5x}{3}+1}\textrm{ is an integer for any }x\in\mathbb{Z}^{+}$ .

$Q(1)$ is true because

$\displaystyle{\frac{(1)^3}{3}+(1)^2+\frac{5(1)}{3}+1}=4$

is an integer.

Assume $Q(x)$ is true for some $x\in\mathbb{Z}^{+}$ .

Then,

$\begin{aligned} &\qquad \frac{(x+1)^3}{3}+(x+1)^2+\frac{5(x+1)}{3}+1 \\ & = \frac{(x^3+3x^2+3x+1)}{3} + (x^2+2x+1)+\frac{(5x+5)}{3} + 1 \\ & = \bigg( \frac{x^3}{3}+x^2+\frac{5x}{3}+1\bigg) + \bigg( \frac{3x^2+3x+1}{3}+2x+1+\frac{5}{3}+1 \bigg) \\ \end{aligned}$

The first term is an integer for $Q(x)$ is assumed to be true. We then need to check whether the second term is of integral value(s).

The second term, after simplification, is

$x^2+3x+4$ ,

obviously an integer.

$\therefore$ $Q(x+1)$ thus holds.

Because $Q(1)$ is true, by mathematical induction, $Q(x)$ is true for all positive integers $x$ .

Escape to the original statement.

$3|n^3+3n^2+5n+3\Longleftrightarrow P(n+1)\textrm{ holds true.}$

Because $P(1)$ is true, by mathematical induction, $P(n)$ is true for any positive integers $n$ .

Prove by mathematical induction that if $n$ is a positive integer, $f(n)\equiv 3^{2n}-1$ is divisible by $8$ .

Solution.

We wish to show that the statement is true for $n=1$ , and also true for $n+1$ .

When $n=1$ , $f(1)=3^{2(1)}-1=8$ is divisible by $8$ .

Assume $f(n)$ is true for some positive integer $n$ , i.e.,

$\{f(n):3^{2n}-1=8m\, |\, \exists \, m, n\in\mathbb{Z}^{+}\}$ .

For $f(n+1)=3^{2(n+1)}-1$ , we have

$\begin{aligned} & \quad 3^{2(n+1)}-1 \\ & = 3^{2n+2} - 1 \\ & = 3^{2n}\cdot 3^2 - 1 \\ & = 9(3^{2n})-1 \\ & = 3^{2n} -1 + 8(3^{2n}) \\ \end{aligned}$

As is assumed $3^{2n}-1$ divisible by $8$ , the statement is thus also true for $n+1$ .

We have proven by mathematical induction that for any positive integer $n\enspace (\in\mathbb{Z}^+)$ , $f(n)$ is divisible by $8$ .

Afterword.

Try to prove $\textrm{\scriptsize{NOT}}$ by mathematical induction $\textrm{\scriptsize{BUT}}$ by direct proof.

$\begin{aligned} &\quad \frac{3^{2n}-1}{8} \\ & = \frac{3^{2n}-1}{9-1} \\ & = \frac{3^{2n}-1}{3^2-1} \\ & = \dots \end{aligned}$

Let $x=3^2$ , then

$\begin{aligned} &\quad \dots \\ & = \frac{x^n-1}{x-1} \\ & = 1+x+x^2+\cdots + x^{n-2} + x^{n-1} \enspace (\in\mathbb{Z}^{+}) \\ \end{aligned}$

$\therefore$ $f(n)\equiv 3^{2n}-1$ is divisible by $8$ .

M	T	W	T	F	S	S
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

Day: November 24, 2021

202111241152 Solution to 1971-CE-AMATH-3

202111241104 Solution to 1969-CE-AMATH-3