Proof and Mathematical Induction

Disprove by counterexample that all values of$2^n$are odd, for$n\ge 1$.

SOLUTION:

If we let$n=2$,$2^2=4$

4 cannot be written as$2n+1$, with$n\in \mathrm{\mathbb{Z}}$.

So 4 is not odd.

We have found a counterexample to disprove the conjecture.

Prove by exhaustion that consecutive positive even numbers under 10, sum even numbers.

SOLUTION:

We want to see that the sum of two consecutive, positive even numbers under 10 is even.

Therefore the numbers we are going to use are 2,4,6 and 8.

$$\begin{gathered} 2+4=6 \\ 4+6=10 \\ 6+8=14 \end{gathered}$$

6, 10 and 14 are all even numbers as they are all multiples of 2:

$$\begin{gathered} 6=2\left(3\right) \\ 10=2\left(5\right) \\ 14=2\left(7\right) \end{gathered}$$

Therefore these sums are all even numbers.

So our conjecture has been proven.

Prove that$\sqrt{2}$is irrational.

SOLUTION:

Firstly let's break down what we are being asked. We want to show that$\sqrt{2}$cannot be written as a fraction.

So let's try and prove it is a fraction and find our contradiction.

Let$\sqrt{2}=\frac{a}{b}$, where$\frac{a}{b}$is a fraction in its' simplest form.

Then if we square both sides:

$2=\frac{a^2}{b^2}$

$2b^2=a^2$

$a$must be even, this is because$a^2$is even and the square root of an even number is even.

Let$a=2k$, $a^2={\left(2k\right)}^2=4k^2$

$\therefore 4k^2=2b^2$

$2k^2=b^2$

This means$b^2$is even. Therefore it means that$b$is even.

If both$a$and$b$are even, this means that$\frac{a}{b}$, is not in its simplest form.

This is a contradiction as we originally assumed$\frac{a}{b}$was in its simplest form.

Therefore$\sqrt{2}$is not rational and is irrational.

Prove by mathematical induction that$f\left(n\right)=5^n+8n+3$is divisible by 4 for all$n\in \mathrm{\mathbb{Z}}+$.

SOLUTION:

Step 1: Firstly we need to test$n=1$, this gives$f\left(1\right)=5^1+8\left(1\right)+3=16=4\left(4\right)$.

So this is a multiple of 4.

Step 2: Assume that when$n=k,$the statement is correct.

If we write this in mathematical notation we get$f\left(k\right)=5^k+8k+3=4m$, where m is a positive number.

Step 3: Now let's use the fact that$n=k$is true to prove that for$n=k+1$:

$f(k+1)=5^{k+1}+8(k+1)+3$

$f(k+1)=\left(5^k\right){\left(5\right)}^1+8k+8+3$

$$\begin{gathered} f(k+1)=5^k(4+1)+8k+8+3 \\ =4\left(5^k\right)+5^k+8k+8+3 \end{gathered}$$

Now we substitute$4m$instead of$5^k+8k+3$in the$f(k+1)$, we get:

$f(k+1)=4m+4\left(5^k\right)+8=4(m+5^k+2)$

Step 4: Therefore based on$f\left(k\right)$being a multiple of 4,$f(k+1)$is a multiple of 4.

So this is true for$n=1$, and for some$n=k$, it is true for some$n=k+1$.

Therefore the conjecture has been proven.

Prove by mathematical induction that$\sum _{r=1}^n\frac{1}{r(r+1)}=\frac{n}{n+1}$for all$n\ge 1$.

SOLUTION:

Step 1: Firstly we need to test the case when$n=1$.

$\sum _1^1\frac{1}{r(r+1)}=\frac{1}{1(1+1)}=\frac{1}{2}=\frac{n}{n+1}$

Step 2: We assume that the case of$n=k$is correct.

$\sum _{r=1}^k\frac{1}{r(r+1)}=\frac{k}{k+1}$

Step 3: Now using the fact we need to test for$n=k+1$:

$$\begin{gathered} \sum _{r=1}^{k+1}\frac{1}{r(r+1)}=\sum _{r=1}^k\frac{1}{r(r+1)}+\frac{1}{(k+1)(k+2)} \\ \sum _{r=1}^k\frac{1}{r(r+1)}+\frac{1}{(k+1)(k+2)}=\frac{1}{(k+1)(k+2)}+\frac{k}{k+1} \end{gathered}$$

If we simplify this out we get:

$$\begin{gathered} \frac{k}{k+1}+\frac{1}{(k+1)(k+2)}=\frac{k(k+2)}{(k+1)(k+2)}+\frac{1}{(k+1)(k+2)} \\ \frac{k(k+2)}{(k+1)(k+2)}+\frac{1}{(k+1)(k+2)}=\frac{k^2+2k+1}{(k+1)(k+2)} \\ \frac{k^2+2k+1}{(k+1)(k+2)}=\frac{(k+1)(k+1)}{(k+1)(k+2)} \end{gathered}$$

If we cancel out the term$(k+1)$from the numerator and denominator we get:

$\frac{(k+1)}{(k+2)}$, if we go back to the fact that$n=k+1$, $\frac{k+1}{k+2}=\frac{n}{n+1}$

Step 4: Therefore it has been proven for when$n=1$, and for some$n=k$it has been proven for$n=k+1$. Therefore it is true for all$n\ge 1$.