Monthly Archives: May 2010

Mathematical Induction Proofs

In this section are completed proofs using induction. As time progresses I will slowly begin to improve the English explanation included in each proof. Below are the proof statements.

I. Bernoulli’s Inequality: If \( x > -1 \) then \( \forall n \in \mathbb{N} \) it is the case that \( \left( 1 + x \right)^n \ge 1 + nx \)

II. Prove that \( n^3 + 5n \) is divisible by \( 6 \ \forall n \in \mathbb{N} \)

III. Prove \( 1^2 – 2^2 +3^2 + \ldots + \left(-1 \right)^{n+1}n^2 = \left(-1 \right)^{n+1} \frac{n \left(n + 1 \right)}2 \ \forall n \in \mathbb{N} \)

IV. Prove using induction $$ E_n \left( x \right) = 1 + x + \frac{ x^2 }{2} + \frac{ x^3 }{3!}+ \cdots + \frac{ x^n }{n!} $$

I. Bernoulli’s Inequality:
If \( x > -1 \) then \( \forall n \in \mathbb{N} \) it is the case that \( \left( 1 + x \right)^n \ge 1 + nx \) \( \left( 1 + x \right)^1 \ge 1 + \left(1 \right) x \) By the inductive hypothesis \( \forall k \in \mathbb{N} \) it is the case that \( \left( 1 + x \right)^k \ge 1 + kx \). Since \( \left( 1 + x \right) > 0 \) it is true that \( \left( 1 + x \right)^k \left( 1 + x \right) \ge \left( 1 + kx \right) \left( 1 + x \right)\) $$ \left( 1 + x \right)^{k + 1} \ge 1 + x + kx + kx^2 = 1 + \left(k + 1 \right)x + kx^2 \ge 1 + \left(k + 1 \right)x $$. Therefore, by mathematical induction Bernoulli’s equation is correct.
II. Prove that \( n^3 + 5n \) is divisible by \( 6 \ \forall n \in \mathbb{N} \)
By definition \( 6 \vert \left(n^3 + 5n \right) \) if and only if there exists some \( m \in \mathbb{Z} \) such that \( n^3 + 5n = 6m \).
\( \left(1 \right)^3 + 5\left(1\right) = 6m \)
By the inductive hypothesis it is true that \( k^3 + 5k = 6m \) for all \( k \in \mathbb{N} \) and for some \( m \in \mathbb{Z} \)
\( k^3 + 5k +3k \left( 3k + 1 \right) + 6= 6m + 3k \left( 3k + 1 \right) + 6 \)
\( \left(k + 1 \right)^3 + 5 \left(k + 1 \right)= 6m + 3k \left( 3k + 1 \right) + 6 \)
If the quantity \( 3k \left( 3k + 1 \right) \) contains a factor of six then the proof is complete.
Since \( k \in \mathbb{Z}\) and since all integers are either even or odd then
i. if \( k \) is even then by definition \( k = 2p \) which implies \( 3k \left(3k + 1 \right) = 6p \left(6p + 1 \right)=6\left(6p + p \right) \)
ii. if \( k \) is odd then by definition \( k = 2p +1 \) which implies \( 3k \left(3k + 1 \right) = \left( 6p +3 \right) \left(6p + 4 \right)=6 \left( 6p^2 +7p + 2 \right) \)
III. Prove \( 1^2 – 2^2 +3^2 + \ldots + \left(-1 \right)^{n+1}n^2 = \left(-1 \right)^{n+1} \frac{n \left(n + 1 \right)}2 \ \forall n \in \mathbb{N} \)
\( \left(-1 \right)^2 1^2 = \left(-1 \right)^2 \frac{1 \left( 1 + 1 \right)}2 \).
By the inductive hypothesis \( \forall k \in \mathbb{N} \) it is the case that \( 1^2 – 2^2 +3^2 + \ldots + \left(-1 \right)^{k+1}k^2 = \left(-1 \right)^{k+1} \frac{k \left(k + 1 \right)}2 \). \( \sum_{l=1}^k \left(-1 \right)^{l+1}l^2 + \left(-1 \right)^{k+2} \left(k+1 \right)^2 = \left(-1 \right)^{k+1} \frac{k \left(k + 1 \right)}2 + \left(-1 \right)^{k+2} \left(k+1 \right)^2 \).
Simplifying the left-hand side and creating a common denominator on the right yields \( \sum_{l=1}^{k+1} \left(-1 \right)^{l+1}l^2 = \left(-1 \right)^{k+1} \frac{k \left(k + 1 \right)}2 + \frac{2 \left(-1 \right)^{k+2} \left(k+1 \right)^2}2 \).
\( \sum_{l=1}^{k+1} \left(-1 \right)^{l+1}l^2 = \left(-1 \right)^{k+1} \left(k+1 \right) \frac{k – 2 \left(k+1 \right)}2 = \left(-1 \right)^{k+1} \left(k+1 \right) \frac{\left(-1 \right) \left(k+2 \right)}2 = \left(-1 \right)^{k+2} \frac{\left(k + 1 \right) \left(k+2 \right)}2 \)
IV. Let \(E_n\) be a sequence of continuous functions defined as $$ E_1 \left( x \right) = 1 + x $$ $$ E_{ n + 1 } = 1 + \int_0^x E_n \left( x \right) \ dt $$ Prove using induction $$ E_n \left( x \right) = 1 + x + \frac{ x^2 }{2} + \frac{ x^3 }{3!}+ \cdots + \frac{ x^n }{n!} $$ \( \forall n \in \mathbb{N} \) and \( \forall x \in \mathbb{R} \)
First show that \( E_1 \) is true.$$ E_1 = 1 + x $$ $$E_2 = 1 + \int_0^x E_1 \left( x \right) \ dt = 1 + x + \frac{ x^2 }{2} $$
Since \(E_1\) is true then by the induction hypothesis $$ E_k \left( x \right) = 1 + \int_0^x E_{k – 1} \left( x \right) \ dt = 1 + x + \frac{ x^2 }{2} + \frac{ x^3 }{3!}+ \cdots + \frac{ x^k }{k!} $$ $$E_k + \frac{ x^{ k + 1 }}{ \left( k + 1 \right)! } = 1 + x + \frac{ x^2 }{2} + \frac{ x^3 }{3!}+ \cdots + \frac{ x^k }{k!} + \frac{ x^{ k + 1 }}{ \left( k + 1 \right)! } = E_{ k + 1 } $$
therefore by mathematical induction
$$ E_n \left( x \right) = 1 + x + \frac{ x^2 }{2} + \frac{ x^3 }{3!}+ \cdots + \frac{ x^n }{n!} $$

Congruence Theorems I-IX

Congruence
Let \(a,b,n \in \mathbb{Z}\) and \(n>0\). \(a\) and \(b\) are congruent modulo \(n\) if and only if \(n \vert \left(a-b \right)\) and it is written
$$a \equiv b\; (\text{mod }n) $$
Algebraic Properties
I. Reflexive: \( n \vert 0 \Rightarrow a \equiv a\; ( \text{mod }n) \)
Proof: By definition \(n \vert 0 \) iff \( \exists k \in \mathbb{Z} \ni 0=nk\) and since \( 0=a-a=nk\) then by definition \(a \equiv a \; ( \text{mod }n) \)
II. Symmetric: \( a \equiv b\; ( \text{mod }n)\ \Rightarrow b \equiv a \; ( \text{mod }n) \)
Proof: By definition \( \left(a-b \right)=nk \) and \( -\left(b-a \right)=n \left(-k\right) \) which implies \(b \equiv a \; ( \text{mod }n) \)
III. Transitive: If \( a \equiv b\; ( \text{mod }n) \) and \( b \equiv c \; ( \text{mod }n) \) then \( a \equiv c \; ( \text{mod }n) \)
Proof: By definition \( \left(a-b \right)=nk\) and \( -\left(b-c \right)=nl\). Also, \(a=nk+b\) and \(c=b-nl\) and \(a-c=nk+b-b+nl=nk+nl=n \left(k+l \right)\) which implies \(a \equiv c\; ( \text{mod }n) \)
IV. If \(a \equiv b\; ( \text{mod }n) \) and \(c \equiv d\; ( \text{mod }n) \) then \(a+c \equiv b+d\; ( \text{mod }n) \)
Proof: By definition \( \left(a-b \right)=nk\) and \( \left(c-d \right)=nl\). Also, \(a=nk+b\) and \(c=d+nl\) and \(a+c=nk+b+d+nl=b+d+nk+nl=\left(b+d \right) + n\left(k+l\right)\) which implies \(a + c \equiv b + d \; ( \text{mod }n) \) since \(\left(a+c \right) – \left(b+d \right) = n\left(k+l\right).\)
V. If \(a \equiv b\; ( \text{mod }n) \) and \(c \equiv d\; ( \text{mod }n) \) then \(a-c \equiv b-d\; ( \text{mod }n) \)
Proof: By definition \( \left(a-b \right)=nk\) and \( \left(c-d \right)=nl\). Also, \(a=nk+b\) and \(c=d+nl\) and \(a-c=nk+b-d-nl=b-d+nk-nl=\left(b-d \right) + n\left(k-l\right)\) which implies \(a – c \equiv b – d\; ( \text{mod }n) \) since \( \left(a-c \right) – \left(b-d \right) = n\left(k-l\right).\)
VI. If \(a \equiv b\; ( \text{mod }n) \) and \(c \equiv d\; ( \text{mod }n) \) then \(ac \equiv bd\; ( \text{mod }n) \)
Proof: By definition \( \left(a-b \right)=nk\) and \( \left(c-d \right)=nl\). Also, \(a=nk+b\) and \(c=d+nl\) and \(ac=\left(nk+b\right)\left(d+nl\right)=dnk+n^2kl+bd+nbl=bd+n\left(dk+nkl+bl\right)\) which implies \(ac \equiv bd \; ( \text{mod }n) \) since \(ac – bd =n \left(dk+nk+bl\right)\)
VII. If \(a \equiv b\; ( \text{mod }n) \) then \(a^k \equiv b^k\; ( \text{mod }n) \)
Proof: By mathematical induction note that \( a^1 \equiv b^1\; ( \text{mod }n) \) is true by definition therefore, by the inductive hypothesis we assume \(a^t \equiv b^t \; ( \text{mod }n) \) to be true for all \(t\) contained in the natural numbers. It must be shown that \(a^{t+1} \equiv b^{t+1}\; ( \text{mod }n) \) is true. Notice \( aa^t=a^{t+1}\) and \( bb^t=b^{t+1}\). Since \( a \equiv b \; ( \text{mod }n)\ \) is true by definition and \(a^t \equiv b^t \; ( \text{mod }n) \) is true by the inductive hypothesis then by theorem VI \(a^{t+1} \equiv b^{t+1}\; ( \text{mod }n) \) is true.
VIII. If \(n\) is a natural number expressed in base \(10\) as \( n= a_k a_{k-1} \cdots a_1 a_0 \) and \( m= a_k + a_{k-1} + \ldots + a_1 + a_0 \) then \( n \equiv m\; ( \text{mod }3) \)
Proof: By definition \( n – m = 10^k a_k + 10^{k-1} a_{k-1} + \ldots + 10 a_1 + a_0 – a_k – a_{k-1} – \ldots – a_1 – a_0\). Simplifying and collecting like terms \(n – m = a_k \left( 10^k – 1 \right) + a_{k-1} \left( 10^{k-1} – 1 \right) + \ldots + a_1 \left ( 10 -1 \right)\) If \( 10^k \equiv 1^k \; (\text{mod }3) \) then \(n – m = a_k \left( 3t_k \right) + a_{k-1} \left( 3t_{k-1} \right) + \ldots + a_1 \left( 3t_1 \right)=3t \) where \( t = \left( a_kt_k + a_{k-1} t_{k-1} + \ldots + a_1 t_1 \right) \in \mathbb{Z}\) therefore, by definition \( n \equiv m \; ( \text{mod }3)\ \)
IX. If \(n\) is a natural number expressed in base \(10\) as \( n= a_k a_{k-1} \cdots a_1 a_0 \) and \( m= a_k + a_{k-1} + \ldots + a_1 + a_0 \) then \( n \equiv m \; ( \text{mod }9) \)
Proof: By definition \( n – m = 10^k a_k + 10^{k-1} a_{k-1} + \ldots + 10 a_1 + a_0 – a_k – a_{k-1} – \ldots – a_1 – a_0\). Simplifying and collecting like terms \(n – m = a_k \left( 10^k – 1 \right) + a_{k-1} \left( 10^{k-1} – 1 \right) + \ldots + a_1 \left ( 10 -1 \right)\) If \( 10^k \equiv 1^k \; ( \text{mod }9) \) then \(n – m = a_k \left( 9t_k \right) + a_{k-1} \left( 9t_{k-1} \right) + \ldots + a_1 \left ( 9t_1 \right)=9t\) where \( t = \left( a_kt_k + a_{k-1} t_{k-1} + \ldots + a_1 t_1 \right) \in \mathbb{Z}\) therefore, by definition \( n \equiv m \; ( \text{mod }9) \)