# Proofs

#### Information

Proofs are used in mathematics in order to shorten the time it takes to complete a future operation as by proving a method works to other mathematicians allows it to be widely used and can save everyone alot of time if it is a shorter method

Below is a simple prrof for finding if everything multiplied by 2 is an even number

First we can define a natuaral numbers as n

Therefore doubling n gives us 2n which is divisible by 2 therefore for n this is correct

Next we do the same operation for n+1 to see if the next number after n is also divisible by 2
2(n+1) = 2n + 2
This is also divisible by 2 and therefore the statement is also true for n+1

Finnaly we do this operation for 1
2×1 = 2
This is divisible by 2 as well and therefore we can state:

For all Natural Numbers multiplying by 2 gives an even number

#### Steps for a proof

First we see if true for a value of 1
Then we see if true for a value of a constant (e.g.n or k)
Next we check for the constant plus 1 (e.g.[n+1] or [k+1])
Finally we write a paragraph about what we have proved and how we have proved it

#### Example 1

Prove:

$$\sum_{r=1}^{n}\frac{1}{r(r+1)} = \frac{n}{n+1}$$

Assume n=1:

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

$$\frac{n}{n+1} = \frac{1}{1+1} = \frac{1}{2}$$

Therefore this is true for n = 1 as both equations have the same answer
Now assume true for n = k

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

Now consider for k+1:

$$\sum_{r=1}^{k+1}\frac{1}{r(r+1)} = \frac{1}{1×2} + \frac{1}{2×3} + \frac{1}{3×4} + ... + \frac{1}{k(k+1)} + \frac{1}{(k+1)(k+2)}$$

As we assumed that for n=k:

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

We can rewrite the equation as:

$$\sum_{r=1}^{k+1}\frac{1}{r(r+1)} = \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)+1}{(k+1)(k+2)} = \frac{k^2+2k+1}{(k+1)(k+2)} = \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2}$$

Now for the other equation:

$$\frac{k+1}{(k+1)+1} = \frac{k+1}{k+2}$$

We once again have the same answer from both equations for k+1 and it is therefore true for k+1 as well

(Must Right This)

But this is given the result with k+1 replacing k
Therefore, if the result is true for n=k it is also true for n = k+1
Since it is true for n=1
By induction it is therefore true for all positive integers n

#### Example 2

Prove that for all positive integers n,

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

First we test for n=1

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

This is true and therefore the statement is true for n=1

Now we assume this is true for n=k

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

Letting n=k+1

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

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

Replacing k with k+1 in:

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

$$1+2+3+4+...+k+(k+1)=(\frac{k+1}{2})([k+1]+1)=(\frac{k+1}{2})(k+2)=\frac{(k+1)(k+2)}{2}$$

This is the same value we got in the other equation therefore the statement is true for k+1

But this is given the result with k+1 replacing k
Therefore, if the result is true for n=k it is also true for n = k+1
Since it is true for n=1
By induction it is therefore true for all positive integers n

#### Example 3

Prove that for all positive integers n:
$$1^2+2^2+3^2+...+n^2=(\frac{n}{6})(n+1)(2n+1)$$

Letting n=1

$$1^2=(\frac{1}{6})(1+1)(2[1]+1)=(\frac{1}{6})(2)(3)=1$$

This is true and therefore the statement is true for n=1

Now we assume this is true for n=k

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

Letting n=k+1

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

Taking common parts outside the brackets

$$=\frac{k+1}{6}[k(2k+1)+6(k+1)]=\frac{k+1}{6}[(2k^2+k)+(6k+6)]$$

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

Replacing k with k+1 in:

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

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

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

This is the same value we got in the other equation therefore the statement is true for k+1

But this is given the result with k+1 replacing k
Therefore, if the result is true for n=k it is also true for n = k+1
Since it is true for n=1
By induction it is therefore true for all positive integers n

#### Example 4

Now we will do a different kind of proof where we are proving we can find a number in a sequence using an equation:

Given:

$$u_{1} = 2, u_{n+1} = 4u_{n} + 3$$

Prove:

$$u_{n} = 3×4^{n-1} - 1$$

First we test for n=1

$$u_{1+1} = 4u_{1} + 3$$

First we test for n=1

$$u_{2} = 4(2) + 3 = 11$$

Now testing:

$$u_{n} = 3×4^{n-1} - 1$$

$$u_{2} = 3×4^{2-1} - 1 = 3×4^{1} - 1 = 12 - 1 = 11$$

This is true and therefore the statement is true for n=1

Now we assume this is true for n=k

$$u_{k+1} = 4u_{k} + 3$$

and

$$u_{k} = 3×4^{k-1} - 1$$

Letting n=k+1

$$u_{k+1} = 3×4^{(k+1)-1} - 1 = 3×4^{k} - 1$$

Replacing k with k+1 in:

$$u_{k+1} = 4u_{k} + 3$$

Using the value of

$$u_{k}$$

$$u_{k+1} = 4(3×4^{k-1} - 1) + 3 = 4(3×4^{k-1} - 1) + 3 = (4×3×4)^{k-1} - 4 + 3 = (4×3×4)^{k-1} - 1$$

Now we need to remember that

$$4^{-1} = \frac{1}{4}$$

and therefore

$$4^{k-1} = \frac{1}{4}(4^k)$$

Employing this knowledge to set the power to k in our equation from k-1 gives:

$$u_{k+1} = \frac{1}{4}(4×3×4^{k}) - 1 = 3×4^{k} - 1$$

Now we have the same value that we got previously and therefore the statement is true for k+1

But this is given the result with k+1 replacing k
Therefore, if the result is true for n=k it is also true for n = k+1
Since it is true for n=1
By induction it is therefore true for all positive integers n

#### Example 5

Prove

$$2^{n+2}+3^{2n+1}$$

is divisible by 7 for all values n ≥ 1

First we let n=1

$$2^{1+2}+3^{2(1)+1} = 2^{3}+3^{3} = 8+27 = 35$$

Now we need to check that 35 is divisible by 7

$$\frac{35}{7} = 5$$

This is divisible by 7 therefore this statement is true for n=1

Now we assume this is true for n=k

$$2^{k+2}+3^{2k+1} = 7m$$

Where m is any integer value (Therefore 7m is always divisible by 7)

We can rearrange this to:

$$3^{2k+1} = 7m - 2^{k+2}$$

Letting n=k+1

$$2^{(k+1)+2}+3^{2(k+1)+1} = 2^{k+3}+3^{2k+3} = 2×2^{k+2} + 3^2×3^{2k+1}$$

Replacing

$$3^{2n+1}$$

with

$$7m - 2^{k+2}$$

from the equation derived above gives us:

(This can be done with the

$$2^{k+2}$$

as well if you rearrange the equation differently)

$$2×2^{k+2} + 3^2×3^{2k+1} = 2×2^{k+2} + 9(7m - 2^{k+2})$$

$$= 2×2^{k+2} + 63m - 9×2^{k+2} = 63m - 7×2^{k+2} = 7(9m - 2^{k+2})$$

This is a multiple of 7 and is therefore divisible by 7 meaning that the expression is true for n=k+1

But this is given the result with k+1 replacing k
Therefore, if the result is true for n=k it is also true for n = k+1
Since it is true for n=1
By induction it is therefore true for all positive integers n

#### Example 6

This final example shows a proof for a matrix

For

$$A=\begin{pmatrix}1 & 2\\\ 0 & 2\end{pmatrix}$$

,Prove that

$$A^n=\begin{pmatrix}1 & 2^{n+1}-2\\\ 0 & 2^n\end{pmatrix}$$

Letting n=1

$$A^1=A=\begin{pmatrix}1 & 2^{1+1}-2\\\ 0 & 2^1\end{pmatrix}=\begin{pmatrix}1 & 2^{2}-2\\\ 0 & 2\end{pmatrix}=\begin{pmatrix}1 & 4-2\\\ 0 & 2\end{pmatrix} =\begin{pmatrix}1 & 2\\\ 0 & 2\end{pmatrix}$$

This is the same value we have for A and therefore it is true for n=1

Now we assume this is true for n=k

$$A^k=\begin{pmatrix}1 & 2^{k+1}-2\\\ 0 & 2^k\end{pmatrix}$$

Letting n=k+1

$$A^{k+1}=\begin{pmatrix}1 & 2^{(k+1)+1}-2\\\ 0 & 2^{k+1}\end{pmatrix}=\begin{pmatrix}1 & 2^{k+2}-2\\\ 0 & 2^{k+1}\end{pmatrix}$$

We know that

$$A×A^k=A^{k+1}$$

,Therefore using this multiplication we can see if we get the same equation for

$$A^{k+1}$$

$$A×A^k=\begin{pmatrix}1 & 2\\\ 0 & 2\end{pmatrix} \begin{pmatrix}1 & 2^{k+1}-2\\\ 0 & 2^k\end{pmatrix}=\begin{pmatrix}1 & 2^{k+2}-2\\\ 0 & 2^{k+1}\end{pmatrix}$$

This is the same expression we found for n=k+1 meaning that the expression is true for n=k+1

But this is given the result with k+1 replacing k
Therefore, if the result is true for n=k it is also true for n = k+1
Since it is true for n=1
By induction it is therefore true for all positive integers n