Example: Ifthen

This statement is 'obviously true', but ifandthenbutso the statement is not true.

Ifandare both greater than or equal to zero then the statement is true.

Formally, ifandthen

Example: Ifthen

Again the statement is true if only positive numbers are considered – it is also true if only negative numbers are considered. If one number is negative and the other is positive then the statement is false.

Takeandthenbut

Example: Ifandare different irrational numbers, thenandare both irrational.

Takeandso thatand so thatandare both rational.

Example: Ifandare different irrational numbers, thenandare both irrational.

Takeandso thatand so thatandare both rational.

]]>This step is labelled {jatex options:inline}P(k){/jatex}.

2. Assume {jatex options:inline}P(m){/jatex} is true for {jatex options:inline}m \ge k{/jatex} then prove {jatex options:inline}P(m+1){/jatex} is true.

A very simple example is: Prove {jatex options:inline}n^2 \gt n{/jatex} for {jatex options:inline}n \gt 1{/jatex}. 1. The basis step. {jatex options:inline}P(2){/jatex} is true since {jatex options:inline}2^2 \gt 2{/jatex}. 2. Assume {jatex options:inline}P(m){/jatex} is true for {jatex options:inline}m \gt 2{/jatex}.

{jatex options:inline}P(m+1){/jatex} is the statement {jatex options:inline}(m+1)^2 \gt (m+1){/jatex}.

Expanding the brackets gives

{jatex options:inline}m^2+2m+1=m+1{/jatex}

Use {jatex options:inline}P(m){/jatex} which states {jatex options:inline}m^2 \gt m{/jatex} to give

{jatex options:inline}m+2m+1=m+1{/jatex}

which simplifies to

{jatex options:inline}3m+1=m+1{/jatex}

This is true for {jatex options:inline}m \gt 2{/jatex} ]]>

1. Define the identity to be proved so that the statement is equivalent to 'is true'.

2. Prove the identity fororto show that the statementoris true.

3. Assuming the statementis true, prove the statement

Example: Use induction to prove the identity

Ifthe identity becomes

sois true.

Suppose then thatis true so that(1)

is the statement that

Addingto both sides of (1) gives

Concentrate on the left hand side.

(2)

Usewithandto obtain

(2) becomesso P(k+1) is proved.

]]>If square diagonal matrices are multiplied (diagonal means that entries on the leading diagonal are non zero egthe result is a diagonal matrix.

If upper triangular matrices – example- are multiplied, the result is an upper triangular matrix and if lower triangular matrices are multiplied, the result is a lower triangular matrix.

Matrix proofs using induction often deal with powers of matrices.

Ifthen

Ifthen entry in the upper right corner ofis 2 and the diagonal entries are 1.

Ifthen entry in the upper right corner ofis 4 and the diagonal entries are 1.

Ifthen entry in the upper right corner ofis 5 and the diagonal entries are 1.

We might speculate that the entry in the upper right corner ofisand and the diagonal entries are 1 and we can prove this by induction. Supposeis the statement ' the entry in the upper right corner ofis'.

Ifthe upper right entry is 2 and the diagonal entries are 1 so the basis step is true.

Suppose P(n) is true so that

is true so the staement is proved by induction.

]]>{jatex options:inline}(1+x)^n=(1+x)^2(1+x)^{n-2} =(1+2x+x^2)(1+x)^{n-2}{/jatex}

{jatex options:inline}\sum_{r=0}^n n \begin{pmatrix}n\\r\end{pmatrix}x^r=(1+2x+x^2) \sum_{r=0}^{n-2} \begin{pmatrix}n-2\\r\end{pmatrix} x^r{/jatex}

{jatex options:inline}\sum_{r=0}^n \begin{pmatrix}n\\r\end{pmatrix}x^r= \sum_{r=0}^{n-2} \begin{pmatrix}n-2\\r\end{pmatrix}x^r + 2 \sum_{r=0}^{n-2} \begin{pmatrix}n-2\\r\end{pmatrix}x^{r+1} + \sum_{r=0}^{n-2} \begin{pmatrix}n-2\\r\end{pmatrix}x^{r+2} {/jatex}

{jatex options:inline}\sum_{r=0}^n \begin{pmatrix}n\\r\end{pmatrix}x^r= \sum_{r=0}^{n-2} \begin{pmatrix}n-2\\r\end{pmatrix}x^r + 2 \sum_{r=1}^{n-1} \begin{pmatrix}n-2\\r-1\end{pmatrix}x^r + \sum_{r=2}^n \begin{pmatrix}n-2\\r-2\end{pmatrix}x^r {/jatex}

Now equating coefficients.

{jatex options:inline}r=0{/jatex}: Both sides equal 1 (last two terms are zero).

{jatex options:inline}r=1{/jatex}: {jatex options:inline}n=(n-2)+2(1){/jatex} (last term is zero).

{jatex options:inline}r \ge 2{/jatex}: {jatex options:inline}\begin{pmatrix}n\\r\end{pmatrix}= \begin{pmatrix}n-2\\r\end{pmatrix}+ 2 \begin{pmatrix}n-2\\r-1\end{pmatrix} + \begin{pmatrix}n-2\\r-2\end{pmatrix} {/jatex} ]]>

Proof

Let {jatex options:inline}P(k){/jatex} be the statement "{jatex options:inline}(1- \frac{1}{2^2})(1- \frac{1}{3^2})(1- \frac{1}{4^2})...(1- \frac{1}{k^2})=\frac{k+1}{2k}{/jatex}".

{jatex options:inline}(1- \frac{1}{2^2})=\frac{2+1}{2 \times 2}=\frac{3}{4}{/jatex} so {jatex options:inline}P(1){/jatex} is true.

Suppose now that {jatex options:inline}P(k){/jatex} is true for {jatex options:inline}n=1,2,...,k{/jatex}. Try and prove true for {jatex options:inline}P(k+1){/jatex}. Then

{jatex options:inline}\begin{equation} \begin{aligned} (1- \frac{1}{2^2})(1- \frac{1}{3^2})...(1- \frac{1}{k^2})(1- \frac{1}{(k+1)^2}) &=\frac{n+1}{2n}(1- \frac{1}{(k+1)^2}) \\ &= (\frac{k^2+2k}{(k+1)^2}(\frac{k+1}{2k})\\ &= \frac{k(k+2)}{(k+1)^2}(\frac{k+1}{2k}) \\ &= \frac{k+2}{2(k+1)}\end{aligned} \end{equation}{/jatex}]]>

Disproving a statement in this way is called 'proof by contradiction'. Proof by contradiction can be a tricky skill to learn.

Example: Prove that ifthenis irrational.

Suppose thatand thatis rational.

We can then writewhereandare integers, so the original equation becomes

Raising both sides to the power ofgives us

This means that amongs all the powers of 3, there is at least one power of 5, and amongst all the powers of 5 there is at least one power of 3. Both of these statements are false, so the statement, 'andis rational' is false.

Example: Prove thatis irrational.

Suppose thatis rational.

Write

Raise 2 to the power of both sides to givethen as beforeand amongst all the powers of 5 there is a power of 2 and amongst all the powers of 2 there is a power of 2.

Both these statements are false, so the statement 'is rational' is false.

]]>The meaning of the theorem is shown in the following diagram.

We can also illustrate with real numbers, which may be considered one dimensional vectors.

Takeand

The proof follows from the dot product ofwith itself.

Square rooting both sides now gives

]]>We can also illustrate with real numbers, which may be considered one dimensional vectors.

Takeand

The proof follows from the dot product ofwith itself.

Square rooting both sides now gives

]]>A triangle has no diagonals, while a square has two and a pentagon has six.

Each vertex is connected by edges of the polygon to two other vertices, so straight lines draw form the first vertex to the other two cannot be interior to the polygon and wont be diagonals. If there are n vertices altogether, a straight line can be drawn from the first vertex to the othervertices. This process can be repeated for all n vertices to givevertices altogether. Since however, a line drawn from vertexto vertexonly retraces the line drawn from vertexto vertex we must divide by two so that diagonals are not duplicated.

There arediagonals altogether.

A proof by induction is also possible.

Letbe the statement 'a polygon withsides hasdiagonals'. If(a triangle) there arediagonals, sois true.

Supposeis true, so that a polygon withsides hasdiagonals. If an extra vertex is added, we can drawlines from this 'extra' vertex to the others, and one side becomes a diagonal. There will be

Henceis true and the statement is proved.

]]>