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}$$
we have already found:
$$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