Proof by induction question. It's been rotting my brain. Question 50 (1 Viewer)

CM_Tutor · Mar 13, 2021

$\textbf{Theorem:} \qquad n^5 + n^3 + 2n \text{ is divisible by 4 for all integers } n\geqslant 1$

$\begin{align*} \textbf{Non-Inductive Proof:} \qquad n^5 + n^3 + 2n &= n(n^4 + n^2 + 2) \\ &= n\left[\left(n^2 + 1\right)\left(n^2 + 2\right) - 2n^2\right] \qquad \qquad \text{. . . . . . . . . (*)} \end{align*}$

$\textbf{Case 1: } \text{$n$ is even}$

$\text{With $n$ being even, we know that $n^2$ is even and so from (*), we have:}$

$\begin{align*} n^5 + n^3 + 2n &= (\text{even term})\left[(\text{odd term})(\text{even term}) - (\text{even term})\right] \\ &= (\text{even term})\left[(\text{even term}) - (\text{even term})\right] \\ &= (\text{even term})(\text{even term}) \end{align*}$

$\text{and since each of these two terms is divisible by 2, their product is divisible by 4}$

$\textbf{Case 2: } \text{$n$ is odd}$

$\text{Using the same method as above, it is clear that $n^5 + n^3 + 2n$ is even, but that doesn't prove it is divisible by 4.}$
$\text{We can put $n=2k+1$, where $k\in\mathbb{Z}^+$, into (*)}:$

$\begin{align*} n^5 + n^3 + 2n &= (2k+1)\left\{\left[(2k+1)^2 + 1\right]\left[(2k+1)^2 + 2\right] - 2(2k+1)^2\right\} \qquad \text{using (*)} \\ &= (2k+1)\left[\left(4k^2 + 4k + 2\right)\left(4k^2 + 4k + 3\right) - 8k^2 - 8k - 2\right] \\ &= (2k+1)\left[2\left(2k^2 + 2k + 1\right)\left(4k^2 + 4k + 3\right) - 2(4k^2 + 4k + 1)\right] \\ &= 2(2k+1)\left[\left(2M + 1\right)\left(4M + 3\right) - (4M+1)\right] \qquad \text{where $M = k^2+ k$, an integer} \\ &= 2(2k+1)\left(8M^2 + 10M + 3 - 4M - 1\right) \\ &= 2(2k+1)\left(8M^2 + 6M + 2\right) \\ &= 4(2k+1)\left(4M^2 + 3M + 1\right) \\ \frac{n^5 + n^3 + 2n}{4} &= (2k+1)(4M^2 + 3M + 1) \qquad \text{which is clearly an integer} \end{align*}$

$\text{These cases prove that $n^5 + n^3 + 2n$ is divisible by 4 when $n$ is even and when $n$ is odd.}$
$\text{As all integers are either odd or even, the result must be true for all integers $n \geqslant 1$}$

$\textbf{Aside:} \qquad \text{Case 1 can be proved more formally as follows:}$

$\begin{align*} \text{With $n$ being even, let $n = 2m$ where $m\in\mathbb{Z}^+$:} \qquad n^5 + n^3 + 2n &= 2m\left\{\left[(2m)^2 + 1\right]\left[(2m)^2 + 2\right] - 2(2m)^2\right\} \qquad \text{using (*)} \\ &= 2m\left[\left(4m^2 + 1\right)\left(4m^2 + 2\right) - 8m^2\right\] \\ &= 2m\left[2\left(4m^2 + 1\right)\left(2m^2 + 1\right) - 8m^2\right\] \\ &= 4m\left[\left(4m^2 + 1\right)\left(2m^2 + 1\right) - 4m^2\right\] \\ \frac{n^5 + n^3 + 2n}{4} &= m\left[\left(4m^2 + 1\right)\left(2m^2 + 1\right) - 4m^2\right\] \qquad \text{which is clearly an integer} \end{align*}$

idkkdi · Mar 13, 2021

CM_Tutor said:
$\textbf{Theorem:} \qquad n^5 + n^3 + 2n \text{ is divisible by 4 for all integers } n\geqslant 1$

$\begin{align*} \textbf{Non-Inductive Proof:} \qquad n^5 + n^3 + 2n &= n(n^4 + n^2 + 2) \\ &= n\left[\left(n^2 + 1\right)\left(n^2 + 2\right) - 2n^2\right] \qquad \qquad \text{. . . . . . . . . (*)} \end{align*}$

$\textbf{Case 1: } \text{$n$ is even}$

$\text{With $n$ being even, we know that $n^2$ is even and so from (*), we have:}$

$\begin{align*} n^5 + n^3 + 2n &= (\text{even term})\left[(\text{odd term})(\text{even term}) - (\text{even term})\right] \\ &= (\text{even term})\left[(\text{even term}) - (\text{even term})\right] \\ &= (\text{even term})(\text{even term}) \end{align*}$
$\text{and since each of these two terms is divisible by 2, their product is divisible by 4}$

$\textbf{Case 2: } \text{$n$ is odd}$

$\text{Using the same method as above, it is clear that $n^5 + n^3 + 2n$ is even, but that doesn't prove it is divisible by 4.}$
$\text{We can put $n=2k+1$, where $k\in\mathbb{Z}^+$, into (*)}:$

$\begin{align*} n^5 + n^3 + 2n &= (2k+1)\left\{\left[(2k+1)^2 + 1\right]\left[(2k+1)^2 + 2\right] - 2(2k+1)^2\right\} \qquad \text{using (*)} \\ &= (2k+1)\left[\left(4k^2 + 4k + 2\right)\left(4k^2 + 4k + 3\right) - 8k^2 - 8k - 2\right] \\ &= (2k+1)\left[2\left(2k^2 + 2k + 1\right)\left(4k^2 + 4k + 3\right) - 2(4k^2 + 4k + 1)\right] \\ &= 2(2k+1)\left[\left(2M + 1\right)\left(4M + 3\right) - (4M+1)\right] \qquad \text{where $M = k^2+ k$, an integer} \\ &= 2(2k+1)\left(8M^2 + 10M + 3 - 4M - 1\right) \\ &= 2(2k+1)\left(8M^2 + 6M + 2\right) \\ &= 4(2k+1)\left(4M^2 + 3M + 1\right) \\ \frac{n^5 + n^3 + 2n}{4} &= (2k+1)(4M^2 + 3M + 1) \qquad \text{which is clearly an integer} \end{align*}$

$\text{These cases prove that $n^5 + n^3 + 2n$ is divisible by 4 when $n$ is even and when $n$ is odd.}$
$\text{As all integers are either odd or even, the result must be true for all integers $n \geqslant 1$}$

$\textbf{Aside:} \qquad \text{Case 1 can be proved more formally as follows:}$

$\begin{align*} \text{With $n$ being even, let $n = 2m$ where $m\in\mathbb{Z}^+$:} \qquad n^5 + n^3 + 2n &= 2m\left\{\left[(2m)^2 + 1\right]\left[(2m)^2 + 2\right] - 2(2m)^2\right\} \qquad \text{using (*)} \\ &= 2m\left[\left(4m^2 + 1\right)\left(4m^2 + 2\right) - 8m^2\right\] \\ &= 2m\left[2\left(4m^2 + 1\right)\left(2m^2 + 1\right) - 8m^2\right\] \\ &= 4m\left[\left(4m^2 + 1\right)\left(2m^2 + 1\right) - 4m^2\right\] \\ \frac{n^5 + n^3 + 2n}{4} &= m\left[\left(4m^2 + 1\right)\left(2m^2 + 1\right) - 4m^2\right\] \qquad \text{which is clearly an integer} \end{align*}$

Induction

(n+1)^5 + (n+1)^3 + 2(n+1)
= (n^5 + n^3 + 2n) + 4(n^4 + 2n^3 + 3n^2) + n^2 (n+1)^2 + 8n + 4

Qeru · Mar 13, 2021

idkkdi said:
Induction

(n+1)^5 + (n+1)^3 + 2(n+1)
= (n^5 + n^3 + 2n) + 4(n^4 + 2n^3 + 3n^2) + n^2 (n+1)^2 + 8n + 4

Damn beat me to it. The proof for why $n^2(n+1)^2$ is divisble by 4:

n is even: let n=2k then the expression becomes: $4k^2(2k+1)^2$

n is odd: let n=2k+1 then the expression becomes: $4(2k+1)^2(k+1)^2$

Trebla · Mar 13, 2021

Qeru said:
Damn beat me to it. The proof for why $n^2(n+1)^2$ is divisble by 4:

n is even: let n=2k then the expression becomes: $4k^2(2k+1)^2$

n is odd: let n=2k+1 then the expression becomes: $4(2k+1)^2(k+1)^2$

Alternatively, note that n(n+1) = 2(1+2+3+...+n)

CM_Tutor · Mar 13, 2021

$\textbf{Theorem:} \qquad n^5 + n^3 + 2n \text{ is divisible by 4 for all integers } n\geqslant 1$

$\textbf{Inductive Proof:} \qquad \text{By induction on $n$:}$

$\textbf{A} \qquad \text{Put $n = 1$}$

$n^5 + n^3 + 2n = 1^5 + 1^3 + 2(1) = 4 \text{, which is divisible by 4}$

$\text{So, the result is true for $n = 1$.}$

$\textbf{B} \qquad \text{Let $k$ be a value of $n$ for which the result is true. That is,}$

$k^5 + k^3 + 2k = 4M \qquad \text{for some integer $M$} \qquad \qquad \text{. . . . . . . . . (**)}$

$\text{We must now prove the result for $n = k + 1$. That is, we must prove that$

$(k+1)^5 + (k+1)^3 + 2(k+1) = 4N \qquad \text{for some integer $N$}$

$\begin{align*} \text{LHS} &= (k+1)^5 + (k+1)^3 + 2(k+1) \\ &= \left(k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1\right) + \left(k^3 + 3k^2 + 3k + 1\right) + 2k + 2 \\ &= k^5 + 5k^4 + 11k^3 + 13k^2 + 10k + 4 \\ &= \left(4M - k^3 - 2k\right) + 5k^4 + 11k^3 + 13k^2 + 10k + 4 \qquad \text{using the induction hypothesis (**)} \\ &= 4M + 5k^4 + 10k^3 + 13k^2 + 8k + 4 \\ &= 4(M + 2k + 1) + 4k^2(k^2 + 2k + 3) + k^4 + 2k^3 + k^2 \\ &= 4\left[M + 2k + 1 + k^2(k^2 + 2k + 3)\right] + k^2(k+1)^2 \\ &= 4\left[M + 2k + 1 + k^2(k^2 + 2k + 3)\right] + 4L^2 \qquad \text{as $k(k+1)$ is even and so putting $2L=k(k+1)$} \\ &= 4N \qquad \text{where $N = M + 2k + 1 + k^2(k^2 + 2k + 3) + L^2$, an integer} \\ &= \text{RHS} \end{align*}$

$\text{So, if the result is true for $n = k$, then it must also be true for $n=k+1$.}$

$\textbf{C} \qquad \text{It follows from } \textbf{A} \text{ and } \textbf{B} \text{ by the process of mathematical induction that the result is true for all integers $n \geqslant 1$}$

CM_Tutor · Mar 13, 2021

Qeru said:
Damn beat me to it. The proof for why $n^2(n+1)^2$ is divisble by 4:

n is even: let n=2k then the expression becomes: $4k^2(2k+1)^2$

n is odd: let n=2k+1 then the expression becomes: $4(2k+1)^2(k+1)^2$

More simply, $n^2(n+1)^2 = \left[n(n+1)\right]^2$ , and $n(n+1)$ , as the product of two consecutive integers, must be even and so its square must be divisible by 4.

CM_Tutor · Mar 13, 2021

An alternative inductive approach:

$\textbf{Theorem:} \qquad n^5 + n^3 + 2n \text{ is divisible by 4 for all integers } n\geqslant 1$

$\textbf{Inductive Proof:} \qquad \text{By induction on $n$:}$

$\textbf{A} \qquad \text{Put $n = 1$:}$

$n^5 + n^3 + 2n = 1^5 + 1^3 + 2(1) = 4 \text{, which is divisible by 4}$

$\text{Put $n = 2$:}$

$n^5 + n^3 + 2n = 2^5 + 2^3 + 2(2) = 32 + 8 + 4 = 44 \text{, which is divisible by 4}$

$\text{So, the result is true for both $n = 1$ and $n = 2$.}$

$\textbf{B} \qquad \text{Let $k$ be a value of $n$ for which the result is true. That is,}$

$k^5 + k^3 + 2k = 4M \qquad \text{for some integer $M$} \qquad \qquad \text{. . . . . . . . . (**)}$

$\text{We must now prove the result for $n = k + 2$. That is, we must prove that$

$(k+2)^5 + (k+2)^3 + 2(k+2) = 4N \qquad \text{for some integer $N$}$

$\begin{align*} \text{LHS} &= (k+2)^5 + (k+2)^3 + 2(k+2) \\ &= \left(k^5 + 10k^4 + 40k^3 + 80k^2 + 80k + 32\right) + \left(k^3 + 6k^2 + 12k + 8\right) + 2k + 4 \\ &= k^5 + 10k^4 + 41k^3 + 86k^2 + 94k + 44 \\ &= \left(4M - k^3 - 2k\right) + 10k^4 + 41k^3 + 86k^2 + 94k + 44 \qquad \text{using the induction hypothesis (**)} \\ &= 4M + 10k^4 + 40k^3 + 86k^2 + 92k + 44 \\ &= 4M + 8k^4 + 40k^3 + 84k^2 + 92k + 44 + 2k^4 + 2k^2 \\ &= 4\left(M + 2k^4 + 10k^3 + 21k^2 + 23k + 11\right) + 2k^2(k^2 + 1) \\ &= 4\left(M + 2k^4 + 10k^3 + 21k^2 + 23k + 11\right) + 2 \times 2L \qquad \text{as either $k^2$ or $k^2+1$ is even, so put $L=\frac{k^2(k^2+1)}{2}$ is an integer} \\ &= 4N \qquad \text{where $N = M + 2k^4 + 10k^3 + 21k^2 + 23k + 11 + L$, an integer} \\ &= \text{RHS} \end{align*}$

$\text{So, if the result is true for $n = k$, then it must also be true for $n=k+2$.}$

$\textbf{C} \qquad \text{It follows from } \textbf{A} \text{ (with $n = 1$) and } \textbf{B} \text{ by the process of mathematical induction that the result is true for all odd integers $n \geqslant 1$.}$
$\text{Further, it follows from } \textbf{A} \text{ (with $n = 2$) and } \textbf{B} \text{ by the process of mathematical induction that the result is true for all even integers $n \geqslant 2$.}$
$\text{Thus, the result is true for all integers $n \geqslant 1$.}$

CM_Tutor · Mar 14, 2021

A much more efficient non-inductive proof:

$\textbf{Theorem:} \qquad n^5 + n^3 + 2n \text{ is divisible by 4 for all integers } n\geqslant 1$

$\textbf{Non-Inductive Proof:}$

$\begin{align*} \qquad n^5 + n^3 + 2n &= n^5 + 2n^4 + n^3 + 2n - 2n^4 \\ &= n^3(n^2 + 2n + 1) - 2n(n^3 - 1) \\ &= n^3(n+1)^2 - 2n(n^3 - 1) \qquad \qquad \text{. . . . . . . . . (*)} \end{align*}$

$\textbf{Case 1: } \text{If $n$ is even, then from (*), the result takes the form:}$

$n^5 + n^3 + 2n = (\text{even term})^3(\text{odd term})^2 - 2(\text{even term})(\text{odd term})$

$\text{So, the first term is divisible by 4 (and, in fact, by 8), and the second term is divisible by 4, and thus the result is true for this case.}$

$\textbf{Case 2: } \text{$n$ is odd, then from (*), the result takes the form:}$

$n^5 + n^3 + 2n = (\text{odd term})^3(\text{even term})^2 - 2(\text{odd term})(\text{even term})$

$\text{So, the first term is divisible by 4 and the second term is divisible by 4, and thus the result is true for this case.}$

$\text{These cases prove that $n^5 + n^3 + 2n$ is divisible by 4 when $n$ is even and when $n$ is odd.}$
$\text{As all integers are either odd or even, the result must be true for all integers $n \geqslant 1$}$

Paradoxica · Mar 14, 2021

Black Magic Proof:

Observe the following identity:

$n^5+n^3+2n \equiv 120\binom{n}{5} + 240\binom{n}{4} + 156\binom{n}{3} + 36\binom{n}{2} + 4\binom{n}{1}$

All coefficients of the binomial sum are multiples of 4, and all binomial coefficients are integers, so the RHS is divisible by 4, hence the LHS must also be divisible by 4.

■

Qeru · Mar 14, 2021

Paradoxica said:
Black Magic Proof:

Observe the following identity:

$n^5+n^3+2n \equiv 120\binom{n}{5} + 240\binom{n}{4} + 156\binom{n}{3} + 36\binom{n}{2} + 4\binom{n}{1}$

All coefficients of the binomial sum are multiples of 4, and all binomial coefficients are integers, so the RHS is divisible by 4, hence the LHS must also be divisible by 4.

■

Wow just wow. Im interested on how thats derived?

Paradoxica · Mar 14, 2021

Qeru said:
Wow just wow. Im interested on how thats derived?

use the greedy algorithm to successively eliminate the highest available power by subtracting the appropriately weighted binomial coefficient

this is a lot of expanding and algebra simplification so it's not that much nicer than splitting into cases and arguing carefully, but it doesn't require a lot of thinking so that is an advantage of this method

also this only works for polynomials

Paradoxica · Mar 14, 2021

actually there is a systematic way of doing this and it's basically the discrete version of the derivative

Define the forward difference operator Δf(n) = f(n+1)-f(n)

the binomial coefficients xCk are the monomial analogues of the continuous monomials x^k /k!

in the sense that Δ(xCk) = (xC[k-1]), much like how D(x^k /k!) = x^[k-1]/(k-1)!

so you can use this to "differentiate" any polynomial expression and obtain the first, second, third, etc. "derivatives"

now observe that in classical calculus that for any polynomial (of degree n) P(x), you can write the polynomial in the following form:

P(0)x⁰/0! + P'(0)x¹/1! + P''(0)x²/2! + P'''(0)x³/3! + ... + P^(n) (0) x^n/n! (this is just the maclaurin series of P(x))

The same thing is true in discrete calculus, that you just evaluate each difference at 0 to obtain the coefficients of the binomial coefficients.

So we proceed, first defining f(x) = x^5 + x^3 + 2x

Δf(x) = 5x⁴ + 10x³ + 13x² + 8x + 4

Δ²f(x) = 20x³ + 60x² + 76x + 36

Δ³f(x) = 60x² + 180x + 156

Δ⁴f(x) = 120x + 240

Δ⁵f(x) = 120

and notice that the constant terms of each of these are the same weights as i have from my previous answer.

change x to n to recover the problem (i kept it the same just to make the analogy clearer)

Proof by induction question. It's been rotting my brain. Question 50 (1 Viewer)

AbstractBlade

New Member

CM_Tutor

Moderator

idkkdi

Well-Known Member

Qeru

Well-Known Member

Trebla

Administrator

CM_Tutor

Moderator

CM_Tutor

Moderator

CM_Tutor

Moderator

CM_Tutor

Moderator

Paradoxica

-insert title here-

Qeru

Well-Known Member

Paradoxica

-insert title here-

Paradoxica

-insert title here-

Users Who Are Viewing This Thread (Users: 0, Guests: 1)