proof-induction-02cad33d-c103-4f86-972b-d0111325c19b

Proof by Induction

1. Mathematical Induction basic proofs

Lets's being with a formula e i π + 1 = 0 e i π + 1 = 0 e^(i pi)+1=0e^{i\pi}+1=0eiπ+1=0 but we can also do
e = lim n → ∞ ( 1 + 1 n ) n e = lim n → ∞   1 + 1 n n e=lim_(n rarr oo)(1+(1)/(n))^(n)e= \lim_{n\to\infty} \left (1+\frac{1}{n} \right)^ne=limn→∞(1+1n)n
Prove that for each integer n ≥ 1 n ≥ 1 n >= 1n \geq 1n≥1,
A ( n ) : 1 + 2 + ⋯ + n = n ( n + 1 ) 2 A ( n ) : 1 + 2 + ⋯ + n = n ( n + 1 ) 2 A(n):1+2+cdots+n=(n(n+1))/(2)A(n): 1 + 2 + \cdots + n = \frac{n(n+1)}{2}A(n):1+2+⋯+n=n(n+1)2

Base Case:

Proving that it works for n = 1 n = 1 n=1n = 1n=1 is the first step in showing the formula works:
For n = 1 n = 1 n=1n = 1n=1:
A ( 1 ) = 1 = 1 ( 1 + 1 ) 2 = 2 2 = 1 A ( 1 ) = 1 = 1 ( 1 + 1 ) 2 = 2 2 = 1 A(1)=1=(1(1+1))/(2)=(2)/(2)=1A(1) = 1 = \frac{1(1+1)}{2} = \frac{2}{2} = 1A(1)=1=1(1+1)2=22=1
Therefore, the base case is true.

Inductive Hypothesis:

The second phase of the proof requires the assumption that the formula is true for any integer n ≥ 1 n ≥ 1 n >= 1n \geq 1n≥1:
A ( n ) = 1 + 2 + ⋯ + n = n ( n + 1 ) 2 A ( n ) = 1 + 2 + ⋯ + n = n ( n + 1 ) 2 A(n)=1+2+cdots+n=(n(n+1))/(2)A(n) = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}A(n)=1+2+⋯+n=n(n+1)2

Inductive Step:

The third phase requires that the formula hold for n + 1 n + 1 n+1n + 1n+1:
A ( n + 1 ) = 1 + 2 + ⋯ + n + ( n + 1 ) A ( n + 1 ) = 1 + 2 + ⋯ + n + ( n + 1 ) A(n+1)=1+2+cdots+n+(n+1)A(n+1) = 1 + 2 + \cdots + n + (n+1)A(n+1)=1+2+⋯+n+(n+1)
Using the inductive hypothesis, we have:
A ( n + 1 ) = n ( n + 1 ) 2 + ( n + 1 ) A ( n + 1 ) = n ( n + 1 ) 2 + ( n + 1 ) A(n+1)=(n(n+1))/(2)+(n+1)A(n+1) = \frac{n(n+1)}{2} + (n+1)A(n+1)=n(n+1)2+(n+1)
Combine the terms and simplify:
A ( n + 1 ) = n ( n + 1 ) + 2 ( n + 1 ) 2 = ( n + 1 ) ( n + 2 ) 2 A ( n + 1 ) = n ( n + 1 ) + 2 ( n + 1 ) 2 = ( n + 1 ) ( n + 2 ) 2 A(n+1)=(n(n+1)+2(n+1))/(2)=((n+1)(n+2))/(2)A(n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}A(n+1)=n(n+1)+2(n+1)2=(n+1)(n+2)2
Thus, the formula holds for n + 1 n + 1 n+1n+1n+1, and by mathematical induction, it holds for all n ≥ 1 n ≥ 1 n >= 1n \geq 1n≥1
% NEXT PROOF
\bigskip
Proposition: If n ∈ N n ∈ N n inNn \in \mathbb{N}n∈N, then
1 + 3 + 5 + 7 + ⋯ + ( 2 n − 1 ) = n 2 . 1 + 3 + 5 + 7 + ⋯ + ( 2 n − 1 ) = n 2 . 1+3+5+7+cdots+(2n-1)=n^(2).1 + 3 + 5 + 7 + \dots + (2n - 1) = n^2.1+3+5+7+⋯+(2n−1)=n2.
Proof: We will prove this by mathematical induction.
Base Case: For n = 1 n = 1 n=1n = 1n=1, the left-hand side is simply the first odd number:
1 = 1 2 . 1 = 1 2 . 1=1^(2).1 = 1^2.1=12.
This is true, so the base case holds.
Inductive Hypothesis: Assume that the formula is true for some arbitrary k k kkk, i.e., assume that:
1 + 3 + 5 + ⋯ + ( 2 k − 1 ) = k 2 . 1 + 3 + 5 + ⋯ + ( 2 k − 1 ) = k 2 . 1+3+5+cdots+(2k-1)=k^(2).1 + 3 + 5 + \dots + (2k - 1) = k^2.1+3+5+⋯+(2k−1)=k2.
This is called the inductive hypothesis.
Inductive Step: We must show that if the formula is true for k k kkk, then it is also true for k + 1 k + 1 k+1k+1k+1. That is, we need to show:
1 + 3 + 5 + ⋯ + ( 2 k − 1 ) + [ 2 ( k + 1 ) − 1 ] = ( k + 1 ) 2 . 1 + 3 + 5 + ⋯ + ( 2 k − 1 ) + [ 2 ( k + 1 ) − 1 ] = ( k + 1 ) 2 . 1+3+5+cdots+(2k-1)+[2(k+1)-1]=(k+1)^(2).1 + 3 + 5 + \dots + (2k - 1) + [2(k+1) - 1] = (k+1)^2.1+3+5+⋯+(2k−1)+[2(k+1)−1]=(k+1)2.
Using the inductive hypothesis, we know:
1 + 3 + 5 + ⋯ + ( 2 k − 1 ) = k 2 . 1 + 3 + 5 + ⋯ + ( 2 k − 1 ) = k 2 . 1+3+5+cdots+(2k-1)=k^(2).1 + 3 + 5 + \dots + (2k - 1) = k^2.1+3+5+⋯+(2k−1)=k2.
Adding the next odd number 2 ( k + 1 ) − 1 = 2 k + 1 2 ( k + 1 ) − 1 = 2 k + 1 2(k+1)-1=2k+12(k+1) - 1 = 2k + 12(k+1)−1=2k+1, we have:
k 2 + ( 2 k + 1 ) . k 2 + ( 2 k + 1 ) . k^(2)+(2k+1).k^2 + (2k + 1).k2+(2k+1).
Simplifying the right-hand side:
k 2 + 2 k + 1 = ( k + 1 ) 2 . k 2 + 2 k + 1 = ( k + 1 ) 2 . k^(2)+2k+1=(k+1)^(2).k^2 + 2k + 1 = (k+1)^2.k2+2k+1=(k+1)2.
Thus, the formula holds for k + 1 k + 1 k+1k+1k+1.
Conclusion: Since the formula holds for n = 1 n = 1 n=1n = 1n=1 (the base case), and we have shown that if it holds for n = k n = k n=kn = kn=k, it must also hold for n = k + 1 n = k + 1 n=k+1n = k+1n=k+1, by the principle of mathematical induction, the formula is true for all n ∈ N n ∈ N n inNn \in \mathbb{N}n∈N.
Therefore, we have proven that:
1 + 3 + 5 + ⋯ + ( 2 n − 1 ) = n 2 . 1 + 3 + 5 + ⋯ + ( 2 n − 1 ) = n 2 . 1+3+5+cdots+(2n-1)=n^(2).1 + 3 + 5 + \dots + (2n - 1) = n^2.1+3+5+⋯+(2n−1)=n2.
\bigskip%NEXTPROOF\documentclass{article}\usepackage{amsmath}
\begin{document}
Proposition: If n n nnn is a non-negative integer, then 5 ∣ ( n 5 − n ) 5 ∣ ( n 5 − n ) 5∣(n^(5)-n)5 \mid (n^5 - n)5∣(n5−n).
Proof: We will prove the proposition by mathematical induction.
Step 1: Base Case ( n = 0 n = 0 n=0n = 0n=0):
We need to check if the proposition holds when n = 0 n = 0 n=0n = 0n=0.
n 5 − n = 0 5 − 0 = 0 n 5 − n = 0 5 − 0 = 0 n^(5)-n=0^(5)-0=0n^5 - n = 0^5 - 0 = 0n5−n=05−0=0
Since 5 5 555 divides 0 0 000, the base case holds true.
Step 2: Inductive Hypothesis:
Assume that the proposition holds for some non-negative integer k k kkk, i.e.,
5 ∣ ( k 5 − k ) 5 ∣ ( k 5 − k ) 5∣(k^(5)-k)5 \mid (k^5 - k)5∣(k5−k)
This means there exists some integer m m mmm such that:
k 5 − k = 5 m k 5 − k = 5 m k^(5)-k=5mk^5 - k = 5mk5−k=5m
Step 3: Inductive Step:
We need to prove that the proposition holds for k + 1 k + 1 k+1k + 1k+1, i.e., we need to show that 5 ∣ ( ( k + 1 ) 5 − ( k + 1 ) ) 5 ∣ ( ( k + 1 ) 5 − ( k + 1 ) ) 5∣((k+1)^(5)-(k+1))5 \mid ((k+1)^5 - (k+1))5∣((k+1)5−(k+1)).
Expand ( k + 1 ) 5 ( k + 1 ) 5 (k+1)^(5)(k+1)^5(k+1)5 using the binomial theorem:
( k + 1 ) 5 = k 5 + 5 k 4 + 10 k 3 + 10 k 2 + 5 k + 1 ( k + 1 ) 5 = k 5 + 5 k 4 + 10 k 3 + 10 k 2 + 5 k + 1 (k+1)^(5)=k^(5)+5k^(4)+10k^(3)+10k^(2)+5k+1(k+1)^5 = k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1(k+1)5=k5+5k4+10k3+10k2+5k+1
Now subtract ( k + 1 ) ( k + 1 ) (k+1)(k+1)(k+1) from this expression:
( k + 1 ) 5 − ( k + 1 ) = ( k 5 + 5 k 4 + 10 k 3 + 10 k 2 + 5 k + 1 ) − ( k + 1 ) ( k + 1 ) 5 − ( k + 1 ) = k 5 + 5 k 4 + 10 k 3 + 10 k 2 + 5 k + 1 − ( k + 1 ) (k+1)^(5)-(k+1)=(k^(5)+5k^(4)+10k^(3)+10k^(2)+5k+1)-(k+1)(k+1)^5 - (k+1) = \left( k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 \right) - (k + 1)(k+1)5−(k+1)=(k5+5k4+10k3+10k2+5k+1)−(k+1)
Simplifying:
( k + 1 ) 5 − ( k + 1 ) = k 5 + 5 k 4 + 10 k 3 + 10 k 2 + 4 k ( k + 1 ) 5 − ( k + 1 ) = k 5 + 5 k 4 + 10 k 3 + 10 k 2 + 4 k (k+1)^(5)-(k+1)=k^(5)+5k^(4)+10k^(3)+10k^(2)+4k(k+1)^5 - (k+1) = k^5 + 5k^4 + 10k^3 + 10k^2 + 4k(k+1)5−(k+1)=k5+5k4+10k3+10k2+4k
Factor out 5 5 555 from the terms where it's present:
( k + 1 ) 5 − ( k + 1 ) = ( k 5 − k ) + 5 ( k 4 + 2 k 3 + 2 k 2 + k ) ( k + 1 ) 5 − ( k + 1 ) = ( k 5 − k ) + 5 ( k 4 + 2 k 3 + 2 k 2 + k ) (k+1)^(5)-(k+1)=(k^(5)-k)+5(k^(4)+2k^(3)+2k^(2)+k)(k+1)^5 - (k+1) = (k^5 - k) + 5(k^4 + 2k^3 + 2k^2 + k)(k+1)5−(k+1)=(k5−k)+5(k4+2k3+2k2+k)
By the inductive hypothesis, we know that 5 ∣ ( k 5 − k ) 5 ∣ ( k 5 − k ) 5∣(k^(5)-k)5 \mid (k^5 - k)5∣(k5−k). Thus, k 5 − k = 5 m k 5 − k = 5 m k^(5)-k=5mk^5 - k = 5mk5−k=5m for some integer m m mmm.
Therefore:
( k + 1 ) 5 − ( k + 1 ) = 5 m + 5 ( k 4 + 2 k 3 + 2 k 2 + k ) ( k + 1 ) 5 − ( k + 1 ) = 5 m + 5 ( k 4 + 2 k 3 + 2 k 2 + k ) (k+1)^(5)-(k+1)=5m+5(k^(4)+2k^(3)+2k^(2)+k)(k+1)^5 - (k+1) = 5m + 5(k^4 + 2k^3 + 2k^2 + k)(k+1)5−(k+1)=5m+5(k4+2k3+2k2+k)
= 5 ( m + k 4 + 2 k 3 + 2 k 2 + k ) = 5 ( m + k 4 + 2 k 3 + 2 k 2 + k ) =5(m+k^(4)+2k^(3)+2k^(2)+k)= 5(m + k^4 + 2k^3 + 2k^2 + k)=5(m+k4+2k3+2k2+k)
Since m + k 4 + 2 k 3 + 2 k 2 + k m + k 4 + 2 k 3 + 2 k 2 + k m+k^(4)+2k^(3)+2k^(2)+km + k^4 + 2k^3 + 2k^2 + km+k4+2k3+2k2+k is an integer, this shows that 5 ∣ ( ( k + 1 ) 5 − ( k + 1 ) ) 5 ∣ ( ( k + 1 ) 5 − ( k + 1 ) ) 5∣((k+1)^(5)-(k+1))5 \mid ((k+1)^5 - (k+1))5∣((k+1)5−(k+1)).
Conclusion:
By the principle of mathematical induction, we have shown that 5 ∣ ( n 5 − n ) 5 ∣ ( n 5 − n ) 5∣(n^(5)-n)5 \mid (n^5 - n)5∣(n5−n) for all non-negative integers n n nnn. Thus, the proposition is true.
\end{document}