Mathematical Proof/Methods of Proof/Proof by Induction

< Mathematical Proof < Methods of Proof

The beauty of induction is that it allows a theorem to be proven true where an infinite number of cases exist without exploring each case individually. Induction is analogous to an infinite row of dominoes with each domino standing on its end. If you want to make all the dominoes fall, you can either:

push on the first one, wait to see what happens, and then check each domino afterwards (which may take a long time if there's an infinite number of dominoes!)
or you can prove that if any domino falls, then it will cause the domino after it to fall. (i.e. if the first one falls then the second one will fall, and if the second one falls then the third one will fall, etc.)

Induction, essentially, is the methodology outlined in point 2.

Parts of Induction

Induction is composed of three parts:

The Base Case (in the domino analogy, this shows the first domino will fall)
The Induction Hypothesis (in the domino analogy, we assume that a particular domino will fall)
The Inductive Step (in the domino analogy, we prove that the domino we assume will fall will cause the next domino to fall)

Weak Induction

Weak induction is used to show that a given property holds for all members of a countable inductive set, this usually is used for the set of natural numbers.

Weak induction for proving a statement $P(n)$ (that depends on $n$ ) relies on two steps:

$P(n)$ is true for a certain base step. Usually the base case is $n=1$ or $n=0$

$P(k)\Rightarrow P(k+1)$ . That is, given that $P(k)$ is true, $P(k+1)$ is also true.

If these two properties hold, one may induce that the property holds for all elements in the set in question. Returning to the example, if you are sure that you called your neighbor, and you knew that everyone who was called in turn called his/her neighbor, then you would be guaranteed that everyone on the block had been called (assuming you had a linear block, or that it curved around nicely).

Examples

The first example of a proof by induction is always 'the sum of the first n terms:'

Theorem 2.4.1. For any fixed

n\in \mathbb {N} ,

\sum _{i=1}^{n}{i}={\frac {n(n+1)}{2}}

Proof:

Base step: $1={\frac {1\cdot 2}{2}}$ , therefore the base case holds.

Inductive step: Assume that $\sum _{i=0}^{n}{i}={\frac {n(n+1)}{2}}$ . Consider $\sum _{i=1}^{n+1}{i}$ .

\sum _{i=1}^{n+1}{i}=\sum _{i=1}^{n}i+(n+1)={\frac {n(n+1)}{2}}+n+1

=({\frac {n}{2}}+1)(n+1)

={\frac {(n+1)(n+2)}{2}}

={\frac {(n+1)((n+1)+1)}{2}}

So the inductive case holds. Now by induction we see that the theorem is true.

Reverse Induction

Reverse induction is a method of using an inductive step that uses a negative in the inductive step. It is a minor variant of weak induction. The process still applies only to countable sets, generally the set of whole numbers or integers, and will frequently stop at 1 or 0, rather than working for all positive numbers.

Reverse induction works in the following case.

The property holds for a given value, say $M$ .

Given that the property holds for a given case, say $n=k+1$ , Show that the property holds for $n=k$ .

Then the property holds for all values $n\leq M$ .

I learnt today from http://people.math.carleton.ca/~ckfong/hs14a.pdf (see example there) that reverse indcution is also usable in the general case: "to establish the validity of a sequence of propositions Pn (n ≥ 1), it is enough to establish the following

(a) Pn is valid for inﬁnitely many n.

(b) If Pn+1 is valid, then so is Pn.

It can be the case that we can easily prove P1 and if P for n=m so P for n=2m. In this case we have (a) for the infinitely many n = 2 exp k (for k >= 0).

Strong Induction

In weak induction, for the inductive step, we only required that for a given $n$ , its immediate predecessor ( $n-1$ ) satisfies the theorem (i.e., $P(n-1)$ is true). In strong induction, we require that not only the immediate predecessor, but all predecessors of $n$ satisfy the theorem. The variation in the inductive step is:

If $P(k)$ is true for all $k<n,$ then $P(n)$ is true.

The reason this is called strong induction is fairly obvious--the hypothesis in the inductive step is much stronger than the hypothesis is in the case of weak induction. Of course, for finite induction it turns out to be the same hypothesis, but in the case of transfinite sets, weak induction is not even well-defined, since some sets have elements that do not have an immediate predecessor.

Transfinite Induction

Used in proving theorems involving transfinite cardinals. This technique is used in set theory to prove properties of cardinals, since there is rarely another way to go about it.

Inductive Set

We first define the notion of a well-ordered set. A set $X$ is well-ordered if there is a total order < on $X$ and that whenever $Y\subset X$ is non-empty, there is a least-element in $Y$ . That is, $\exists p\in Y$ such that $p<q\ \forall q\in Y$ .

An inductive set is a set $A\subset X$ such that the following hold:

$\alpha \in A$ (where $\alpha$ is the least element of $X$ )
If $\beta \in A$ then $\forall \gamma \in X$ such that $\beta <\gamma ,\gamma \in A$

Of course, you look at that and say "Wait a minute. That means that $A=X$ !" And, of course you'd be right. That's exactly why induction works. The principle of induction is the theorem that says:

Theorem 2.4.2. If

X

is a non-empty well-ordered set and

A\subset X

is an inductive subset of

X

then

A=X

The proof of this theorem is left as a very simple exercise. Here we note that the set of natural numbers is clearly well-ordered with the normal order that you are familiar with, so $\mathbb {N}$ is an inductive set. If you accept the axiom of choice, then it follows that every set can be well-ordered.

Exercises

Show that this identity holds for all positive integers:

  $1 + 2 + 3 + \dots + n = n(n + 1) / 2$

First, we show that it holds for integers 1, 2 and 3

1 = 2×1/2

1 + 2 = 3×2/2

1 + 2 + 3 = 4×3/2 = 6

Suppose the identiy holds for some number k, then

1+2+3+...+k={\frac {1}{2}}(k+1)k

is true.

We aim to show that:

1+2+3+...+k+(k+1)={\frac {1}{2}}(k+2)(k+1)

is also true. We proceed

{\begin{matrix}1+2+3+...+k&&=&{\frac {1}{2}}(k+1)k\\\\1+2+3+...+k&+(k+1)&=&{\frac {1}{2}}(k+1)k+(k+1)\\\\&&=&(k+1)({\frac {k}{2}}+1)\\\\&&=&{\frac {1}{2}}(k+1)(k+2)\end{matrix}}

which is what we have set out to show. Since the identity holds for 3, it also holds for 4 and since it holds for 4 it also holds for 5, and 6 and 7 and so on.

Show that

n! > 2 n for n \geq 4

The claim is true for n = 4. As 4! > 2⁴, i.e. 24 > 16. Now suppose it's true for n = k, k ≥ 4, i.e.

k! > 2^k

it follows that

(k+1)k! > (k+1)2^k > 2^k+1

(k+1)! > 2^k+1

We have shown that if for n = k then it's also true for n = k + 1. Since it's true for n = 4, it's true for n = 5, 6, 7, 8 and so on for all n.

Show that:

  $13 + 2 3 + \dots + n 3 = (n+1)²n² / 4$

First, we show that this statement holds for n=1.

1^{3}=1

{\frac {(1+1)^{2}(1^{2})}{4}}=1

Suppose it's true for n = k, i.e.

1^{3}+2^{3}+...+k^{3}={\frac {(k+1)^{2}k^{2}}{4}}

it follows that

{\begin{matrix}1^{3}+2^{3}+...+k^{3}+(k+1)^{3}&=&{\frac {(k+1)^{2}k^{2}}{4}}+(k+1)^{3}\\&=&(k+1)^{2}({\frac {k^{2}}{4}}+(k+1))\\&=&{\frac {1}{4}}(k+1)^{2}(k^{2}+4k+4)\\&=&{\frac {1}{4}}(k+1)^{2}(k+2)^{2}\end{matrix}}

We have shown that if it's true for n = k then it's also true for n = k + 1. Now it's true for n = 1 (clear). Therefore it's true for all integers.

Prove for every positive integer n:

2 + 4 + 6 + \dots + 2k = k(k + 1)

$2+4+6+...+2n=n(n+1)$

First, we show that this statement holds for n=1.

2=1\times 2

Assume that the equation holds for n=k. Then,

2+4+6+...+2k=k(k+1)

We aim to show that $2+4+6+...+2k+2(k+1)=(k+1)(k+2)$ .

Adding $2(k+1)$ to both sides,

2+4+6+...+2k+2(k+1)=k(k+1)+2(k+1)

2+4+6+...+2k+2(k+1)=(k+1)(k+2)

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb {N}$ .

Prove for every positive integer n:

1 + 4 + 7 + \dots + (3n - 2) = n(3n - 1) / 2

$1+4+7+...+(3n-2)={\frac {1}{2}}n(3n-1)$

First, we show that this statement holds for n=1.

1={\frac {1}{2}}\times 1(3-1)=1

Assume that the equation holds for n=k. Then,

1+4+7+...+(3k-2)={\frac {1}{2}}k(3k-1)

We aim to show that $1+4+7+...+(3k-2)+(3k+1)={\frac {1}{2}}(k+1)(3k+2)$ .

Adding $3(k+1)-2=3k+1$ to both sides,

1+4+7+...+(3k-2)+(3k+1)={\frac {1}{2}}k(3k-1)+(3k+1)

1+4+7+...+(3k-2)+(3k+1)={\frac {1}{2}}(3k^{2}-k+6k+2)={\frac {1}{2}}(3k^{2}+5k+2)={\frac {1}{2}}(k+1)(3k+2)

1+4+7+...+(3k-2)+(3k+1)={\frac {1}{2}}(k+1)(3k+2)

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb {N}$ .

Prove for every positive integer n:

2 + 7 + 12 + \dots + (5n - 3) = n(5n - 1) / 2

$2+7+12+...+(5n-3)={\frac {1}{2}}n(5n-1)$

First, we show that this statement holds for n=1.

2={\frac {1}{2}}\times 1(5-1)=2

Assume that the equation holds for n=k. Then,

2+7+12+...+(5k-3)={\frac {1}{2}}k(5k-1)

We aim to show that $2+7+12+...+(5k-3)+(5(k+1)-3)={\frac {1}{2}}(k+1)(5(k+1)-1)$ , same as $2+7+12+...+(5k-3)+(5k+2)={\frac {1}{2}}(k+1)(5k+4)$ .

Adding $5(k+1)-3=5k+2$ to both sides,

2+7+12+...+(5k-3)+(5k+2)={\frac {1}{2}}k(5k-1)+(5k+2)

2+7+12+...+(5k-3)+(5k+2)={\frac {1}{2}}(5k^{2}-k+10k+4)={\frac {1}{2}}(5k^{2}+9k+4)={\frac {1}{2}}(k+1)(5k+4)

2+7+12+...+(5k-3)+(5k+2)={\frac {1}{2}}(k+1)(5k+4)

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb {N}$ .

Prove for every positive integer n:

1 + 2 \cdot 2 + 3 \cdot 22 + 4 \cdot 23 + \dots + n \cdot 2 n-1 = 1 + (n-1)2 n

$1+2\cdot 2+3\cdot 2^{2}+4\cdot 2^{3}+...+n\cdot 2^{n-1}=1+(n-1)2^{n}$ ;

First, we show that this statement holds for n=1.

1=1+(1-1)2^{1}=1

Assume that the equation holds for n=k. Then,

1+2\cdot 2+3\cdot 2^{2}+4\cdot 2^{3}+...+k\cdot 2^{k-1}=1+(k-1)2^{k}

We aim to show that $1+2\cdot 2+3\cdot 2^{2}+4\cdot 2^{3}+...+k\cdot 2^{k-1}+(k+1)\cdot 2^{(k+1)-1}=1+((k+1)-1)2^{(k+1)}$ , same as $1+2\cdot 2+3\cdot 2^{2}+4\cdot 2^{3}+...+k\cdot 2^{k-1}+(k+1)\cdot 2^{k}=1+(k)2^{k+1}$ .

Adding $(k+1)\cdot 2^{(k+1)-1}=(k+1)\cdot 2^{k}$ to both sides,

1+2\cdot 2+3\cdot 2^{2}+4\cdot 2^{3}+...+k\cdot 2^{k-1}+(k+1)\cdot 2^{k}=1+(k-1)2^{k}+(k+1)\cdot 2^{k}=1+(k+1+k-1)\cdot 2^{k}=1+(2k)\cdot 2^{k}=1+k\cdot 2^{k+1}

1+2\cdot 2+3\cdot 2^{2}+4\cdot 2^{3}+...+k\cdot 2^{k-1}+(k+1)\cdot 2^{k}=1+(k)2^{k+1}

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb {N}$ .

Prove for every positive integer n:

12 + 2 2 + 3 2 + \dots + n 2 = n(n+1)(2n+1) / 6

$1^{2}+2^{2}+3^{2}+...+n^{2}={\frac {1}{6}}n(n+1)(2n+1)$

First, we show that this statement holds for n=1.

1^{2}={\frac {1}{6}}1(1+1)(2+1)=1

Assume that the equation holds for n=k. Then,

1^{2}+2^{2}+3^{2}+...+k^{2}={\frac {1}{6}}k(k+1)(2k+1)

We aim to show that $1^{2}+2^{2}+3^{2}+...+k^{2}+(k+1)^{2}={\frac {1}{6}}(k+1)((k+1)+1)(2(k+1)+1)$ , same as $1^{2}+2^{2}+3^{2}+...+k^{2}+(k+1)^{2}={\frac {1}{6}}(k+1)(k+2)(2k+3)$ .

Adding $(k+1)^{2}$ to both sides,

${\begin{matrix}1^{2}+2^{2}+3^{2}+...+k^{2}+(k+1)^{2}&=&{\frac {1}{6}}k(k+1)(2k+1)+(k+1)^{2}\\\ &=&{\frac {1}{6}}(k(k+1)(2k+1)+6(k+1)^{2})\\\ &=&{\frac {1}{6}}((k+1)(k(2k+1)+6(k+1)))\\\ &=&{\frac {1}{6}}((k+1)(2k^{2}+k+6k+6))\\\ &=&{\frac {1}{6}}((k+1)(2k^{2}+7k+6))\\\ &=&{\frac {1}{6}}((k+1)(k+2)(2k+3))\end{matrix}}$

1^{2}+2^{2}+3^{2}+...+k^{2}+(k+1)^{2}={\frac {1}{6}}(k+1)(k+2)(2k+3)

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb {N}$ .

Prove for every positive integer n:

1 / 1 \cdot 2 + 1 / 2 \cdot 3 + 1 / 3 \cdot 4 + \dots + 1 / n \cdot (n+1) = n / n+1

${\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+...+{\frac {1}{n\cdot (n+1)}}={\frac {n}{n+1}}$

First, we show that this statement holds for n=1.

{\frac {1}{1\cdot 2}}={\frac {1}{1+1}}

Assume that the equation holds for n=k. Then,

{\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+...+{\frac {1}{k\cdot (k+1)}}={\frac {k}{k+1}}

We aim to show that ${\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+...+{\frac {1}{k\cdot (k+1)}}+{\frac {1}{(k+1)\cdot ((k+1)+1)}}={\frac {(k+1)}{(k+1)+1}}$ , same as ${\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+...+{\frac {1}{k\cdot (k+1)}}+{\frac {1}{(k+1)\cdot (k+2)}}={\frac {k+1}{k+2}}$ .

Adding ${\frac {1}{(k+1)\cdot (k+2)}}$ to both sides,

${\begin{matrix}{\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+...+{\frac {1}{k\cdot (k+1)}}+{\frac {1}{(k+1)\cdot (k+2)}}&=&{\frac {k}{k+1}}+{\frac {1}{(k+1)\cdot (k+2)}}\\\ &=&{\frac {1+(k)(k+2)}{(k+1)\cdot (k+2)}}\\\ &=&{\frac {k^{2}+2k+1}{(k+1)\cdot (k+2)}}\\\ &=&{\frac {(k+1)^{2}}{(k+1)\cdot (k+2)}}\\\ &=&{\frac {(k+1)}{(k+2)}}\end{matrix}}$

{\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+...+{\frac {1}{k\cdot (k+1)}}+{\frac {1}{(k+1)\cdot (k+2)}}={\frac {k+1}{k+2}}

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb {N}$ .

This problem can be solved without mathematical induction. We note that ${\frac {1}{n\cdot (n+1)}}={\frac {1}{n}}-{\frac {1}{n+1}}$ . Then, the question can be paraphrased as ${\frac {1}{1}}-{\frac {1}{2}}+{\frac {1}{2}}-{\frac {1}{3}}+{\frac {1}{3}}-{\frac {1}{4}}+...+{\frac {1}{n}}-{\frac {1}{n+1}}={\frac {n}{n+1}}$ , which simplfies to ${\frac {1}{1}}-{\frac {1}{n+1}}={\frac {n}{n+1}}$ , or ${\frac {n+1-1}{n+1}}={\frac {n}{n+1}}$ . Q.E.D.

Prove for every positive integer n:

3 + 3 2 + 3 3 + \dots + 3 n = 3 \cdot 3 n-1 / 2

$3+3^{2}+3^{3}+...+3^{n}={\frac {3}{2}}(3^{n}-1)$

First, we show that this statement holds for n=1.

3={\frac {3}{2}}(3^{1}-1)=3

Assume that the equation holds for n=k. Then,

3+3^{2}+3^{3}+...+3^{k}={\frac {3}{2}}(3^{k}-1)

We aim to show that $3+3^{2}+3^{3}+...+3^{k}+3^{k+1}={\frac {3}{2}}(3^{k+1}-1)$ .

Adding $3^{k+1}$ to both sides,

${\begin{matrix}3+3^{2}+3^{3}+...+3^{k}+3^{k+1}&=&{\frac {3}{2}}(3^{k}-1)+3^{k+1}\\\ &=&{\frac {3}{2}}(3^{k}-1+{\frac {2}{3}}\cdot 3^{k+1})\\\ &=&{\frac {3}{2}}(3^{k}-1+2\cdot 3^{k})\\\ &=&{\frac {3}{2}}(3\cdot 3^{k}-1)\\\ &=&{\frac {3}{2}}(3^{k+1}-1)\end{matrix}}$

3+3^{2}+3^{3}+...+3^{k}+3^{k+1}={\frac {3}{2}}(3^{k+1}-1)

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb {N}$ .

This can also be proven using the sum formula for a geometric series.

Prove for every positive integer n:

(1+2^{5}+...+n^{5})+(1+2^{7}+...+n^{7})=2\left[{\frac {n(n+1)}{2}}\right]^{4}

$(1+2^{5}+...+n^{5})+(1+2^{7}+...+n^{7})=2\left[{\frac {n(n+1)}{2}}\right]^{4}$

First, we show that this statement holds for n=1.

1+1=2\left[{\frac {1(1+1)}{2}}\right]^{4}=2

Assume that the equation holds for n=k. Then,

(1+2^{5}+...+k^{5})+(1+2^{7}+...+k^{7})=2\left[{\frac {k(k+1)}{2}}\right]^{4}

We aim to show that $(1+2^{5}+...+k^{5}+(k+1)^{5})+(1+2^{7}+...+k^{7}+(k+1)^{7})=2\left[{\frac {(k+1)(k+2)}{2}}\right]^{4}$ .

Adding $(k+1)^{5}+(k+1)^{7}$ to both sides,

${\begin{matrix}(1+2^{5}+...+k^{5}+(k+1)^{5})+(1+2^{7}+...+k^{7}+(k+1)^{7})&=&2\left[{\frac {k(k+1)}{2}}\right]^{4}+(k+1)^{5}+(k+1)^{7}\\\ &=&{\frac {1}{8}}k^{4}(k+1)^{4}+(k+1)^{5}+(k+1)^{7}\\\ &=&{\frac {1}{8}}(k+1)^{4}(k^{4}+8(k+1)+8(k+1)^{3})\\\ &=&{\frac {1}{8}}(k+1)^{4}(k^{4}+8k+8+8k^{3}+24k^{2}+24k+8)\\\ &=&{\frac {1}{8}}(k+1)^{4}(k^{4}+8k^{3}+24k^{2}+32k+16)\\\ &=&{\frac {1}{8}}(k+1)^{4}(k+2)^{4}\\\ &=&2\left[{\frac {(k+1)(k+2)}{2}}\right]^{4}\end{matrix}}$

(1+2^{5}+...+k^{5}+(k+1)^{5})+(1+2^{7}+...+k^{7}+(k+1)^{7})=2\left[{\frac {(k+1)(k+2)}{2}}\right]^{4}

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb {N}$ .

Prove for every positive integer n:

1+r+r^{2}+...+r^{n-1}={\frac {1-r^{n}}{1-r}}

$1+r+r^{2}+...+r^{n-1}={\frac {1-r^{n}}{1-r}}$

First, we show that this statement holds for n=1.

1={\frac {1-r^{1}}{1-r}}=1

Assume that the equation holds for n=k. Then,

1+r+r^{2}+...+r^{k-1}={\frac {1-r^{k}}{1-r}}

We aim to show that $1+r+r^{2}+...+r^{k-1}+r^{k}={\frac {1-r^{k+1}}{1-r}}$ .

Adding $r^{k}$ to both sides,

${\begin{matrix}1+r+r^{2}+...+r^{k-1}+r^{k}&=&{\frac {1-r^{k}}{1-r}}+r^{k}\\\ &=&{\frac {1-r^{k}+(1-r)r^{k}}{1-r}}\\\ &=&{\frac {1-r^{k}+r^{k}-r^{k+1}}{1-r}}\\\ &=&{\frac {1-r^{k+1}}{1-r}}\end{matrix}}$

1+r+r^{2}+...+r^{k-1}+r^{k}={\frac {1-r^{k+1}}{1-r}}

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb {N}$ .

This problem can be solved without using mathematical induction.

$1+r+r^{2}+...+r^{n-1}={\frac {1-r^{n}}{1-r}}$

multiply both sides by ${1-r}$

$(1+r+r^{2}+...+r^{n-1})(1-r)=1-r^{n}$

expand,

$((1-r)+(r-r^{2})+(r^{2}-r^{3})...(r^{n-1}-r^{n})=1-r^{n}$

and simplify.

$1-r^{n}=1-r^{n}$ . Q.E.D.

Prove for every positive integer n:

(1+x)^{n}\geq 1+nx

x\geq -1

(the so called Bernoulli's inequality)

$(1+x)^{n}\geq 1+nx$ if $x\geq -1$

First, we show that this statement holds for n=1.

(1+x)^{1}\geq 1+1\times x

because

(1+x)^{1}=1+1\times x

Assume that the equation holds for n=k. Then,

(1+x)^{k}\geq 1+kx

We aim to show that $(1+x)^{k+1}\geq 1+(k+1)x$ .

Multyplying $(1+x)$ by both sides, (desn't alter the sign of the inequality because $x\geq -1$ , and so $x+1\geq 0$ )

${\begin{matrix}(1+x)^{k+1}&\geq &(1+kx)\cdot (1+x)\\\ &=&1+kx+x+kx^{2}\\\ &=&1+(k+1)x+kx^{2}\\\ &\geq &1+(k+1)x\end{matrix}}$

The last step relies on the fact that $kx^{2}\geq 0$ , since $k \ge 0$ and a square is always greater than or equal to 0.

(1+x)^{k+1}\geq 1+(k+1)x

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb {N}$ .

Prove for every positive integer n:

1^{3}+2^{3}+...+(n-1)^{3}<{\frac {1}{4}}n^{4}<1^{3}+2^{3}+...+n^{3}

$1^{3}+2^{3}+...+(n-1)^{3}<{\frac {1}{4}}n^{4}<1^{3}+2^{3}+...+n^{3}$

First, we show that this statement holds for n = 1 and n = 2.

(1-1)^{3}<{\frac {1}{4}}1^{4}<1^{3}

because

0<{\frac {1}{4}}<1

(1-1)^{3}+1^{3}<{\frac {1}{4}}2^{4}<1^{3}+2^{3}

because

1<4<9

Assume that the inequality holds for n=k. Then,

1^{3}+2^{3}+...+(k-1)^{3}<{\frac {1}{4}}k^{4}<1^{3}+2^{3}+...+k^{3}

We aim to show that $1^{3}+2^{3}+...+k^{3}<{\frac {1}{4}}(k+1)^{4}$ and ${\frac {1}{4}}(k+1)^{4}<1^{3}+2^{3}+...+(k+1)^{3}$

We know that $1^{3}+2^{3}+...+k^{3}<{\frac {1}{4}}k^{4}+k^{3}$ (added $k^{3}$ to both sides of $1^{3}+2^{3}+...+(k-1)^{3}<{\frac {1}{4}}k^{4}$ ).

Now we need to show that ${\frac {1}{4}}k^{4}+k^{3}<{\frac {1}{4}}(k+1)^{4}$

${\frac {1}{4}}k^{4}+k^{3}<{\frac {1}{4}}(k+1)^{4}\Leftrightarrow {\frac {1}{4}}(k^{4}+4k^{3})<{\frac {1}{4}}(k^{4}+4k^{3}+6k^{2}+4k+1)\Leftrightarrow 0<{\frac {1}{4}}(6k^{2}+4k+1)$

The last statement is clearly true ( $k>0$ ). Therefore, ${\frac {1}{4}}k^{4}+k^{3}<{\frac {1}{4}}(k+1)^{4}$ and thus $1^{3}+2^{3}+...+k^{3}<{\frac {1}{4}}k^{4}+k^{3}<{\frac {1}{4}}(k+1)^{4}$ .

Now we show that ${\frac {1}{4}}(k+1)^{4}<1^{3}+2^{3}+...+(k+1)^{3}$ . We know that ${\frac {1}{4}}k^{4}+(k+1)^{3}<1^{3}+2^{3}+...+(k+1)^{3}$ (added $(k+1)^{3}$ to both sides of ${\frac {1}{4}}k^{4}<1^{3}+2^{3}+...+k^{3}$ ). Now we need to show that ${\frac {1}{4}}(k+1)^{4}<{\frac {1}{4}}k^{4}+(k+1)^{3}$

${\begin{matrix}{\frac {1}{4}}(k+1)^{4}<{\frac {1}{4}}k^{4}+(k+1)^{3}&\Leftrightarrow &{\frac {1}{4}}(k^{4}+4k^{3}+6k^{2}+4k+1)<{\frac {1}{4}}(k^{4}+4(k^{3}+3k^{2}+3k+1))\\\ &\Leftrightarrow &{\frac {1}{4}}(k^{4}+4k^{3}+6k^{2}+4k+1)<{\frac {1}{4}}(k^{4}+4k^{3}+12k^{2}+12k+4)\\\ &\Leftrightarrow &0<{\frac {1}{4}}(6k^{2}+8k+3)\end{matrix}}$

The last statement is clearly true ( $k>0$ ). Therefore, ${\frac {1}{4}}(k+1)^{4}<{\frac {1}{4}}k^{4}+(k+1)^{3}$ and thus ${\frac {1}{4}}(k+1)^{4}<1^{3}+2^{3}+...+(k+1)^{3}$ .

Multyplying $(1+x)$ by both sides, (desn't alter the sign of the inequality because $x\geq -1$ , and so $x+1\geq 0$ ) Combining both inequalities we proved, we get the one we needed for the inductive step.

1^{3}+2^{3}+...+k^{3}<{\frac {1}{4}}(k+1)^{4}

and

{\frac {1}{4}}(k+1)^{4}<1^{3}+2^{3}+...+(k+1)^{3}

and by mathematical induction, the formula holds for all $n\in \mathbb {N}$ .

Prove for every positive integer n:

1+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}+...+{\frac {1}{\sqrt {n}}}\leq 2{\sqrt {n}}-1

(Hard)

$1+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}+...+{\frac {1}{\sqrt {n}}}\leq 2{\sqrt {n}}-1$

First, we show that this statement holds for n = 1.

1\leq 2{\sqrt {n}}-1

because

1\leq 1

Assume that the inequality holds for n=k. Then,

1+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}+...+{\frac {1}{\sqrt {k}}}\leq 2{\sqrt {k}}-1

We aim to show that $1+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}+...+{\frac {1}{\sqrt {k}}}+{\frac {1}{\sqrt {k+1}}}\leq 2{\sqrt {k+1}}-1$

We know that $1+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}+...+{\frac {1}{\sqrt {k}}}+{\frac {1}{\sqrt {k+1}}}\leq 2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}-1$ (added ${\frac {1}{\sqrt {k+1}}}$ to both sides of $1+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}+...+{\frac {1}{\sqrt {k}}}\leq 2{\sqrt {k}}-1$ ).

Now we need to show that $2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}-1\leq 2{\sqrt {k+1}}-1$

${\begin{matrix}\ 2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}-1\leq 2{\sqrt {k+1}}-1&\Leftrightarrow &2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}\leq 2{\sqrt {k+1}}\\\ &\Leftrightarrow &2{\sqrt {k\cdot (k+1)}}+1\leq 2(k+1)\\\ &\Leftrightarrow &2{\sqrt {k\cdot (k+1)}}\leq 2k+1\\\ &\Leftrightarrow &2^{2}\cdot {\sqrt {k\cdot (k+1)}}^{2}\leq {(2k+1)}^{2}\\\ &\Leftrightarrow &4k^{2}+4k\leq 4k^{2}+4k+1\\\ &\Leftrightarrow &0\leq 1\end{matrix}}$

The last statement is clearly true. Therefore, $2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}-1\leq 2{\sqrt {k+1}}-1$ and thus $1+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}+...+{\frac {1}{\sqrt {k}}}+{\frac {1}{\sqrt {k+1}}}\leq 2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}-1\leq 2{\sqrt {k+1}}-1$ , the inductive step, and by mathematical induction, the formula holds for all $n\in \mathbb {N}$ .

Prove for every positive integer n: 3 is a factor of

n^{3}-n+3

No Solutions Available

Prove for every positive integer n: 9 is a factor of

10^{n+1}+3\cdot 10^{n}+5

No Solutions Available

Prove for every positive integer n: 4 is a factor of

5^{n}-1

No Solutions Available

Prove for every positive integer n:

x-y

is a factor of

x^{n}-y^{n}

No Solutions Available

Prove for every positive integer n:

7^{2n}-48n-1

is divisible by 2304

No Solutions Available

Find

n_{0}\in \mathbb {N}

such that the inequality

n!>2^{n}

holds for all

n\geq n_{0}

, and give a proof by induction.

No Solutions Available

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.