Вашата кошница е празна
Induction (higher level courseware)
Induction is a useful method for solving problems by generalizing the results of some individual cases. This way we obtain a conjecture which we can accept as true after we verify it.
Example 1
We have \latex{ n } lines in the plane, all of which intersect at a single point \latex{ P }. How many regions they divide the plane into?
Solution
Take a look at only a few lines.
\latex{ 1 } line divides the plane into \latex{ 2 } regions.
By adding a second and third line we get \latex{ 4 } and \latex{ 6 } regions, respectively.
When adding a fourth line, observe that the point \latex{ P } divides it into two rays which both divides one region into two parts, thus the number of regions increase by \latex{ 2 }, to an overall number of \latex{ 8 }. (Figure 1)
\latex{ 1 } line: \latex{ 2 } regions
\latex{ 2 } line: \latex{ 4 } regions
\latex{ 3 } line: \latex{ 6 } regions
\latex{ 4 } line: \latex{ 8 } regions
\latex{ P }
\latex{ P }
\latex{ P }
\latex{ P }
Figure 1
Consider the sequence of adding new lines one by one:
\latex{ 1 } line \latex{\longrightarrow} \latex{ 2 } lines \latex{\longrightarrow} \latex{ 3 } lines \latex{\longrightarrow \dots}
In the first few steps we can observe that the number of regions is twice the number of lines. \latex{ 3 } lines divide the plane into \latex{ 6 } regions, the \latex{4^{th}} line increases the number of regions by \latex{ 2 }, to a total of \latex{ 8 }. Similarly we can advance from the nth element to the \latex{(n + 1)^{th}} for arbitrary \latex{ n: } suppose that for \latex{ n } lines the number of regions is \latex{ 2n }. Then line \latex{n + 1} divides two regions into two parts thus increasing the number of regions by \latex{ 2 }:
\latex{2n + 2 = 2 \times (n + 1).}
This way we can validate for any \latex{ n } that \latex{ n } lines intersecting at a single point divide the plane into \latex{ 2n } regions.
⯁ ⯁ ⯁
The idea of the proof was to determine the first few elements of a sequence and then give a method to step from one element of the sequence to the next one – thus we can reach any element of the sequence.
This method of proof can be very useful for proving propositions which depend on a positive integer \latex{ n }.
PRINCIPLE OF INDUCTION: A proposition which depends on positive integer \latex{ n } is given.
- Prove the proposition for \latex{n = 1};
- Prove that if the proposition holds for \latex{ n } (induction hypothesis), then it also holds for \latex{n + 1.}
By doing this, the proposition is proven for every positive integer \latex{ n }.
The principle of induction can be illustrated, for example, with an (in theory, infinite) line of dominoes. If the first domino falls and any falling domino tosses the next one, then all of the dominoes will fall.
Example 2
By ordering pebbles in a triangular figure such a way that there is one more pebble in each row, we get the triangular numbers:
\latex{ 1 }
\latex{ 1 + 2 = 3 }
\latex{ 1 + 2 + 3 = 6 }
\latex{ 1 + 2 + 3 + 4 = 10 }
\latex{ 1 + 2 + 3 + 4 + 5= 15 }
What is the \latex{ 100^{th} } triangular number? What is the \latex{ n^{th} } triangular number?
Solution
Computing the \latex{100^{th}} triangular number in the form \latex{1 + 2 + 3 + 4 +\dotsc + 98 + 99 +100} is quite time consuming. It makes sense to try to find a formula for determining it.
Take two copies of the number ordered in a triangular figure and place them on top of each other (Figure 2). This way we get a rectangle and we can conjecture that the nth triangular number is:
\latex{1+2+3+4+\dotsc+n=\frac{n\times (n+1)}{2}}.
We will prove the conjecture by induction:
For \latex{n=1:\;\;1=\frac{1\times 2}{2},} the statement is valid.
For \latex{n=1:\;\;1=\frac{1\times 2}{2},} the statement is valid.
Suppose that the statement is valid for \latex{ n }, that is
\latex{1+2+\dotsc+n=\frac{n\times (n+1)}{2},}
Figure 2
and we have to prove it for \latex{ n + 1 }:
\latex{1+2+\dotsc+n+(n+1)=\frac{(n+1)\times (n+2)}{2}}.
The \latex{(n +1)^{th}} triangular number is: \latex{1+2+\dotsc+n+(n+1)}. By the induction hypothesis we can substitute \latex{\frac{n\times (n+1)}{2}} for the sum of the first \latex{ n } elements, thus getting
\latex{1+2+\dotsc +n+(n+1)=\frac{n\times (n+1)}{2}+(n+1)=}
\latex{=\frac{n\cdot (n+1)+2\times (n+1)}{2}=\frac{(n+1)\times (n+2)}{2}.}
The conjecture is proved.
Using the formula one can easily compute the sum of the first \latex{ 100 } positive integers:
\latex{\frac{100\times101}{2}=5,050.}
Example 3
Compute the sum of the cubes of the first \latex{ 100 } positive integers!
Solution
First compute the sum for smaller numbers:
\latex{n=1:1^3=1;}
\latex{n=2:1^3+2^3=9;}
\latex{n=3:1^3+2^3+3^3=36}
\latex{n=4:1^3+2^3+3^3+4^3=100}
After a few try we can conjecture that the sum of cubes will be a square number. Which numbers’ squares are there?
Take a look at the following figure. We illustrated the cubic numbers with cubes (only the first three for convenience). The cubes were then divided into layers of unit width, some layers of the even numbered cubes were cut further on and finally the pieces were built into a square.
Figure 3
For \latex{ n = 3 } the side of the square is \latex{ 1 + 2 + 3 }, which means \latex{1^3 + 2^3 + 3^3 = (1 + 2 + 3)^2}. We conjecture that the sum of the first \latex{ n } positive integers’ cubes is the square of the \latex{ n^{th} } triangular number. Using the formula obtained for the \latex{ n^{th} } triangular number in the previous example we can conjecture the following:
\latex{1^3+2^3+3^3+\dotsc+(n-1)^3+n^3=\left[\frac{n\times (n+1)}{2} \right]^2\;\;\;(n\in \N^+) .}
We will prove this by induction.
For \latex{n=1:\;\;1^3=\left(\frac{1\times 2}{2} \right)^2}, the statement is true.
Suppose that the statement is true for \latex{ n } (induction hypothesis):
Suppose that the statement is true for \latex{ n } (induction hypothesis):
\latex{1^3+2^3+3^3+\dotsc+(n-1)^3+n^3=\left[\frac{n\times (n+1)}{2} \right]^2.}
We want to verify this for \latex{ n + 1 }, that is, we want to prove that the following equality is true:
\latex{1^3+2^3+3^3+\dotsc+(n-1)^3+n^3+(n+1)^3=\left[\frac{(n+1)\times (n+2)}{2} \right]^2.}
Using the induction hypotesis, we can substitute the formula for the sum of the first \latex{ n } summands on the left hand side:
\latex{1^3+2^3+3^3+\dotsc+(n-1)^3+n^3+(n+1)^3=\left[\frac{n\times (n+1)}{2} \right]^2+(n+1)^3=}
\latex{ 1 }
\latex{ 2 }
\latex{ 3 }
\latex{ n }
\latex{ 2 }
\latex{ 4 }
\latex{ 6 }
\latex{ 2n }
\latex{ 3 }
\latex{ 6 }
\latex{ 9 }
\latex{ 3n }
\latex{ 3n }
\latex{ 2n }
\latex{ n }
\latex{ n^2 }
\latex{ 3 }
\latex{ 6 }
\latex{ 9 }
\latex{ 6 }
\latex{ 3 }
\latex{ 2 }
\latex{ 4 }
\latex{ 2 }
\latex{ 1 }
\latex{ n }
\latex{ 2n }
\latex{ 3n }
\latex{ n^2 }
\latex{ 3n }
\latex{ 2n }
\latex{ n }
\latex{=\frac{n^2\times(n+1)^2+4\times (n+1)^3}{4} =\frac{(n+1)^2\times (n^2+4n+4)}{4}=}
\latex{=\frac{(n+1)^2\times (n+2)^2}{4}= \left[\frac{(n+1)\times (n+2)}{2} \right]^2. }
The conjecture is verified for every positive integer \latex{ n }.
We can see that the hardest part was to find the appropriate conjecture.
Induction can be useful for solving divisibility problems too.
Example 4
Prove that \latex{4^n + 15n – 1} is divisible by 9 for every \latex{n\in \N^+}.
Solution
We will prove by induction:
For \latex{ n = 1 } the proposition is that \latex{4^1 + 15 - 1 = 18} is divisible by \latex{ 9 }, which is true.
Suppose that \latex{9\mid 4^n+15n-1,} and prove that
\latex{9\mid 4^{n+1}+15\times (n+1)-1.}
We modify the expression \latex{4^{n+1}+15\times (n+1)-1.} so that \latex{4^n + 15n - 1} is a part of it since we know by the induction hypothesis that it is divisible by \latex{ 9 }.
\latex{4^{n+1}+15\times (n+1)-1=4\times 4^n+15n+15-1=}
\latex{=4\times (4^n+15n-1)-4\times 15n+4+15n+14=}
\latex{=4\times (4^n+15n-1)-45n+18=4\times (4^n+15n-1)-9\times (5n-2)}.
\latex{=4\times (4^n+15n-1)-4\times 15n+4+15n+14=}
\latex{=4\times (4^n+15n-1)-45n+18=4\times (4^n+15n-1)-9\times (5n-2)}.
The first part of the subtraction is divisible by \latex{ 9 } according to the induction hypothesis. The second part is a multiple of \latex{ 9 } thus is divisible by \latex{ 9 } as well, which means that the difference is also divisible by \latex{ 9 }.
Therefore \latex{4^n + 15n – 1} is divisible by \latex{ 9 } for every \latex{n\in \N^+}.
⯁ ⯁ ⯁
Examine how many squares we can end up with if we start to divide a square into smaller squares
Figure 4
One square can be divided into \latex{ 4 } smaller squares, and then any of those can be divided into four parts. This way the number of squares can be increased by \latex{ 3 }, we can end up with \latex{ 1; 4; 7;\, … } squares (Figure 4). The squares are not necessarily congruent.
By dividing the sides of the square into equal parts and joining these points parallel to the sides we divide the square into \latex{ 9 }; \latex{ 16;\, …} squares, the number of small squares is square number (Figure 5).
By deleting a couple of squares from the previous two divisions we can end up with \latex{ 6 } or \latex{ 8 } squares
Figure 5
By dividing any square into \latex{ 4 } smaller ones, we can get \latex{ 11 } squares from \latex{ 8, 12 } from \latex{ 9 } and \latex{ 13 } from \latex{ 10 } etc. We conjecture that for any \latex{n\geq 6} it is possible to divide a square into \latex{ n } smaller squares.
Example 5
Prove that for any \latex{n\geq 6} it is possible to divide a square into \latex{ n } smaller squares.
Solution
We prove this by induction. Since we can go in steps of three in the sequence, the proof will consist of three parts: numbers in the form of \latex{n = 3k, n = 3k + 1} and \latex{n = 3k + 2.}
For \latex{ k = 2 }: a square can be divided into \latex{ 6,\, 7 } or \latex{ 8 } smaller squares (Figures 4 and 5).
Suppose that the statement is true for k: a square can be divided into \latex{n = 3k, n = 3k + 1} and \latex{n = 3k + 2} squares, and prove that this is true for \latex{ k + 1 }: a square can be divided into \latex{3\times(k + 1) = 3k + 3, 3\times(k + 1) + 1 = 3k + 1 + 3, 3\times(k + 1) + 2 = 3k + 2 + 3} squares. Since these can be obtained from the previous divisions by dividing a square into four smaller ones, we proved the conjecture.
In the previous example one can see that if we consider the induction for \latex{ n }, we go in steps of three every time instead of one. In this case we have to verify the conjecture for three consecutive steps at the start of the sequence. Induction can be used this way as well.
\latex{ 6 }
\latex{ 7 }
\latex{ 8 }
\latex{ 9 }
\latex{ 10 }
\latex{ 11 }
Exercises
{{exercise_number}}. Prove that for any positive integer \latex{ n: }
\latex{\frac{1}{1\times 2}+\frac{1}{2\times 3}+\frac{1}{3\times 4}+\dotsc+\frac{1}{n\times (n+1)} =\frac{n}{n+1}}.
{{exercise_number}}. Prove that for any positive integer
- \latex{ 19 } is a divisor of \latex{5^{2n-1}\times 2^{n+1}+3^{n+1}\times 2^{2n-1}}.
- \latex{ 11 } is a divisor of \latex{6^{2n}+3^{n+2}+3^n}.
- \latex{ 17 } is a divisor of \latex{5^{5n+3}+5^{n}\times 3^{n+2}}.
{{exercise_number}}. Is it true for every natural number \latex{n\geq 6} that an equilateral triangle can be cut into \latex{ n } equilateral triangles?
{{exercise_number}}. Planet Bog's currency is the dig. In the bank there are only \latex{ 3 } and \latex{ 5 } dig notes, but from these they have ample amounts.
- Is it possible for them to pay \latex{ 2,014 } digs?
- Is it possible for them to pay \latex{ 2,019 } digs?
- Is it true that the bank can pay any sum greater than \latex{ 5 } digs?
{{exercise_number}}. We start with one piece of paper. In each step, we can tear any piece into \latex{ 3 } pieces. At one point, Stevie counted these pieces of paper and he said ‘At this moment there are exactly \latex{ 2,014 } pieces.' Ann told him that he is mistaken. Who was mistaken?
{{exercise_number}}. We start with one piece of paper. In each step, we can tear any piece into either \latex{ 4 } or \latex{ 6 } pieces.
- Is it possible to end up with \latex{ 2,014 } pieces?
- Is it possible to end up with \latex{ 2,019 } pieces?
- Is it true that the number of pieces can be any positive integer?
{{exercise_number}}. What patterns can be observed in the following sums and how can we compute them? Prove your conjectures.
- \latex{ 1;\,\,\,\,\, 2 + 3 + 4;\,\,\,\,\, 3 + 4 + 5 + 6 + 7;\,\,\,\,\, 4 + 5 + 6 + 7 + 8 + 9 + 10; \,… }
- \latex{1^2;\,\,\,\,\, 1^2 -2^2;\,\,\,\,\, 1^2 - 2^2 + 3^2;\,\,\,\,\, 1^2 - 2^2 + 3^2 -4^2;\, …}
\latex{ - }
\latex{ + }
\latex{ - }
\latex{ = - }
{{exercise_number}}. Prove the following inequalities for every positive integer \latex{ n: }
- \latex{\frac{1}{\sqrt{1} }+\frac{1}{\sqrt{2}}+\dotsc+\frac{1}{\sqrt{n}}\geq \sqrt{n};}
- \latex{2^n\geq 2n}
{{exercise_number}}. Divide the plane with \latex{n(n\in\N^+)} lines into as many regions as possible. How many regions will be there?
{{exercise_number}}. What is the maximal number of regions which \latex{ n } circles divide the plane into? Is it possible to colour these regions with two colours such that neighbouring regions (regions with joint border) have different colours? What about the case of \latex{ n } triangles?
{{exercise_number}}. Show that for every positive integer \latex{n\geq 4 } there exists a convex \latex{ n }-sided polygon with exactly \latex{ 3 } acute angles. (Is it possible to have more than \latex{ 3 } acute angles?)
{{exercise_number}}. The following weights are given: \latex{ 1;\, 2;\, 22;\, … ;\, 2^n }. Show that using only these weights it is possible to measure any integer weighted mass up to \latex{ 2^{n+1}– 1 }.
Puzzle
The shattered vase.
‘Yesterday I arrived home from my shift a bit earlier than usual. I have just taken my seat at the table and started my dinner when something fell in the next room. I rushed there to see what happened and just witnessed a man jumping out of the window, and my wife’s favourite vase lying shattered on the floor. I pursued the man but as I got to the street my glasses fogged up. You know, recently the evenings have become cold. I stumbled upon the rake, I fell and missed the burglar. Please, do accept this case, because this man must have wanted to steal all our belongings. Furthermore I have to tell my wife, who is coming home from her parents today, how has the vase broken.’
‘I don’t understand you’ said the officer, ‘how can you be so afraid from your wife that you dare misleading a detective by a made-up story of a burglar, instead of telling her the truth.’
‘I don’t understand you’ said the officer, ‘how can you be so afraid from your wife that you dare misleading a detective by a made-up story of a burglar, instead of telling her the truth.’
Why was the officer not willing to investigate this case?