Proofs by Induction
Not what you're looking for?
I'm having a hard time comprehending how to write proofs by induction. I'm looking for answers to these problems so that I may have a better understanding of how they are done.
---
All problems need to be proved using induction in proofs.
1. Consider n infinitely long straight lines, none of which are parallel and no three of which have a common point of intersection. Show that for n >= 1, the lines divide the plane into (n^2 + n + 2)/2 separate regions.
2. A string of 0s and 1s is to be processed and converted to an even-parity string by adding a parity bit to the end of the string. The parity bit is initially 0. When a 0 character is processed, the parity bit remains unchanged. When a 1 character is processed, the parity bit is switched from 0 to 1 or from 1 to 0. Prove that the number of 1s in the final string, that is, including the parity bit, is always even.
3. A simple closed polygon consists of n points in the plane joined in pairs by n line segments; each point is the endpoint of exactly two line segments.
a) Use the first principle of induction to prove that the sum of the interior angles of an n-sided simple closed polygon is (n-2)180° for all n >= 3.
b) Use the second principle of induction to prove that the sum of the interior angles of an n-sided simple closed polygon is (n-2) 180° for all n >= 3.
4. In any group of k people, k >= 1, each person is to shake hands with every other person. Find a formula for the number of handshakes, and prove the formula using induction.
5. Prove that any amount of postage greater than or equal to 12 cents can be built using only 4-cent and 5-cent stamps.
Purchase this Solution
Solution Preview
See the attached file for the same text. I suggest that after you read the beginning explanation of proof by induction, you go over questions 4 and 5. Even though they are the last questions, I think they are the easiest.
Proving something by induction takes two steps. First you have to show that the statement is true for n = 1. Then, you have to show that assuming the statement is true for any number n = k, it is also true for n = k + 1. (You can also prove something by induction in a slightly different way: see question 3b.)
To see how this works, think of the first few possible values of n and k. If you prove something is true for n = 1, and if the fact that it is true for n = 1 implies that it is true for n = 2, then it is true for n = 2. The fact that it is true for n = 2 implies it is true for n = 3, which implies it is true for n = 4, and so on.
1. Consider n infinitely long straight lines, none of which are parallel and no three of which have a common point of intersection. Show that for n ≥ 1, the lines divide the plane into (n^2 + n + 2)/2 separate regions.
(1) If n = 1, the plane is divided into 2 regions. The statement is true for n = 1 because
(1)2 + (1) + 2 = 4/2 = 2
2
(2) Now, let's assume that the statement is true for n = 1, 2, 3, ..., k. We're going to show that it's also true for n = k + 1:
When there are k lines, the plane is divided into
k2 + k + 2 regions.
2
If you add another line, you're adding k + 1 more regions. (You can see this by looking at pictures....what happens when you add a 2nd, 3rd, or 4th line?)
So, for n = k + 1, the number of regions is:
k2 + k + 2 + (k + 1)
2
Moving numbers around, we can rearrange the equation:
k2 + k + 2 + k + 1 = k2 + k + 2 + 2k + 2 = k2 + 2k + 1 + k + 1 + 2 = (k+ 1)2 + (k + 1) ...
Purchase this Solution
Free BrainMass Quizzes
Graphs and Functions
This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.
Multiplying Complex Numbers
This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.
Probability Quiz
Some questions on probability
Solving quadratic inequalities
This quiz test you on how well you are familiar with solving quadratic inequalities.
Know Your Linear Equations
Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.