There are infinitely many stations on a train route. Suppose
that the train stops at the first station and suppose
that if the train stops at a station, then it stops at the next
station. Show that the train stops at all stations.
Let P(n) be the statement that the train stops at station n. We want to prove that P(n) is true for all positive integers n. For the basis step, we are told that P(1) is true. For the inductive step, we are told that P(k) implies P(k+1) for each k≥1. Therefore by the principle of mathematical induction, P(n) is true for all positive integers n.
Let P(n) be the statement that 12+22+⋯+n2=n(n+ 1) (2n+1)/6 for the positive integer n. a) What is the statement P(1)? b) Show that P(1) is true, completing the basis step of a proof that P(n) is true for all positive integers n. c) What is the inductive hypothesis of a proof that P(n) is true for all positive integers n? d) What do you need to prove in the inductive step of a proof that P(n) is true for all positive integers n? e) Complete the inductive step of a proof that P(n) is true for all positive integers n, identifying where you use the inductive hypothesis. f) Explain why these steps show that this formula is true whenever n is a positive integer.
a)P(1)=12=12=1(1+1)(2+1)/6 b)P(1)=12=1(1+1)(2+1)/6=1(2)(3)/6=1 c) That P(k) is true for all arbitrary integer k, that is
12+22+⋯+k2=6k(k+1)(2k+1)
d) We want to show that for each k≥1 that P(k) implies P(k+1).
In other words, we want to show that assuming the inductive hypothesis (part C) that we can show
e) The left hand side of part d shows k(k+1)(2k+1)/6+(k+1)2. We need to do a bit of algebraic manipulation to get it into the desired form: factor out (k+1)/6 and then factor the rest.
f) We have completed both the basis step and the inductive step, so by the principle of mathematical induction, the statement is true for every positive integer n.
a)2+4+6+8+...+n=n(n+1) b)
Proof by induction. Base Case:P(1)=1(2)=2 Induction Hypothesis:P(k) implies P(k+1) where P(k)=2+4+6+8+...+k=k(k+1) and P(k+1)=2+4+6+8+...+(k+1)=(k+1)(k+2). Induction Step:
a)21+41+⋯+2n1=2n2n−1. b) Proof by induction. Base Case:P(1)=21=2121−1=21. Induction Hypothesis:P(k) implies P(k+1) where P(k)=21+41+⋯+2k1=2k2k−1 and P(k+1)=21+41+⋯+2(k+1)1=2(k+1)2(k+1)−1.
where n is an integer and greater than 1. a) What is the statement P(2)? b) Show that P(2) is true, completing the basis step of
the proof. c) What is the inductive hypothesis? d) What do you need to prove in the inductive step? e) Complete the inductive step. f) Explain why these steps show that this inequality is
true whenever n is an integer greater than 1.
a)P(2)=1+41<2−21 b)P(2)=45<46. This is true because 45 is less than 46. c) Inductive hypothesis is P(k) which is the mathematical statement that 1+41+91+⋯+k21<2−k1 d) That P(k)→P(k+1) where P(k+1) is the mathematical statement 1+41+91+⋯+(k+1)21<2−(k+1)1 for k≥2. e) Starting with the lefthand side of P(k+1)
Assume inductive hypothesis. Add (k+1)21 to both sides of the inequality.
Partial fraction decomposition of −k1+(k+1)21 from line 1.
Combine kk+1−k+11.
We note k2+k+1>k2+k (it's greater than 1). Since k+11 is being multiplied by something greater than 1, this means that what is being subtracted from 2 in the simplify step is larger than what is being subtracted from 2 in the final step, so the inequality holds.
f) We've completed the basis and inductive step, so by the prinicipal of mathematical induction, the statement is true for every positive integer n>1.
Base Case:P(4)=11≤16 Inductive Hypothesis:P(k)=2k+3≤2k Inductive Step: We aim to prove that 2k+3≤2k→2(k+1)+3≤2(k+1).
Consider 2(k+1)+3=2k+2+3=2k+5. By the inductive hypothesis 2k+5≤2k+2 (because k>3). Since n≥1, this in turn is at most 2n+2n=2n+1, precisely the statement we wanted to prove.
Theorem:1+nh≤(1+h)n for all nonnegative integers h and n. Base Case:P(0)=1+0(0)≤(1+0)0=1≤1. Inductive Hypothesis:P(k)=1+kh≤(1+h)k. Inductive Step: We aim to prove P(k)→P(k+1). P(k+1) is the statement 1+(k+1)h≤(1+h)k+1.
Since h>−1 it follows that 1+h>0, so we can multiply both sides of the inductive hypothesis by 1+h to obtain (1+h)(1+kh)≤(1+h)k+1. To complete the proof it is enough to show that 1+(k+1)h≤(1+h)(1+kh). The right-hand side of this inequality is the same as 1+h+kh+kh2=1+(k+1)h+kh2, which is greater than or equal to 1+(k+1)h because kh2≥0.
Base Case:P(1)=1>2(2−1)≈.8284.... Inductive Hypothesis:P(k)=1+21+31+⋯+k1>2(k+1−1) Inductive Step: We aim to prove P(k)→P(k+1). P(k+1) is the statement 1+21+31+⋯+k+11>2(k+2−1).
By the inductive hypothesis we know that
Base Case:P(1)=12+1=2 is divisible by 2. Inductive Hypothesis: We assume P(k)=k2+k divides 2 is true. Inductive Step: We aim to prove P(k)→P(k+1) where P(k+1)=(k+1)2+(k+1) divides 2 is true.
We observe that k(k+1) is divisible by 2 by the inductive hypothesis. We must show that (k+1)2+(k+1) is divisible by 2 2. We see that (k+1)2+(k+1)=k2+2k+1+k+1=(k2+k)+2(k+1). k2+k is divisibly by 2 by the inductive hypothesis, and 2(k+1) is divisible by 2 by definition, so the sum of two multiples of 2 must be divisible by 2.
The first step uses our induction hypothesis, P(k). The second step uses the fact that 2k+22k+3>1 for all k≥1 (Since its being multiplied by a number less than 1, it will just become smaller and smaller and its on the smaller side of the inequality..). Therefore, b y induction the proposition P(k) is true for all k≥1, and the claim is proved. ■
¶ Discrete Mathematics with Applications, Fifth Edition Section 5.2
Prove by induction that 11n−6 is divisible by 5 for every positive integer n.
Let P(n) by the mathematical statement
11n−6 is divisible by 5 .
Base Case:P(1)=111−6=5 which is divisible by 5 so P(1) is true. Induction Hypothesis: Assume that P(k) is correct for some positive integer k. That means 11k−6 is divisible by 5 and hence 11k−6=5m for some integer m. So 11k=5m+6.
Induction Step: We want to show that 11k+1−6 can be expressed as a multiple of 5, so we will start with the formula 11k+1−6 and we will rearrange it into something involving multiples of 5. At some point we will also want to use the assumption that 11k=5m+6.
11k+1−6=(11×11k)−6by the laws of powers=11(5m+6)−6by the induction hypothesis=11(5m)+66−6by expanding the bracket=5(11m)+60=5(11m+12)since both parts of the formula have a common factor of5
As 11m+12 is an integer we have that 11k+1−6 is divisible by 5, so P(k+1) is correct. Hence by mathematical induction P(n) is correct for all positive integers n.
Prove by induction that 2n>2n for every positive integer n>2
Base Case: P(3) = 23>2(3)=8>6 Induction Hypothesis: Assume that P(k) is correct for some positive integer k>3. That means 2k>2k. Induction Step: We want to show that 2k+1>2(k+1).
Theorem: For all n∈N,03+13+23+⋯+n3=[n(n+1)/2]2. Proof: Base Case:P(0)=03=(0×20+1)2=0 Inductive Hypothesis:P(k) implies P(k+1) where P(k)=03+13+23+⋯+k3=[k(k+1)/2]2 and P(k+1) = 03+13+23+⋯(k+1)3=[(k+1)((k+1)+1)/2]2=[(k+1)((k+2)/2]2. Inductive Step:
Theorem: For all n∈N, 0⋅1+1⋅2+2⋅3+⋯+n(n+1)=3n(n+1)(n+2). Proof: Base Case:P(0)=0(0+1)=30(0+1)(0+2)=0. Inductive Hypothesis:P(k) implies P(k+1) where P(k)=0⋅1+1⋅2+2⋅3+⋯+k(k+1)=3k(k+1)(k+2) and P(k+1)=0⋅1+1⋅2+2⋅3+⋯+(k+1)(k+2)=3(k+1)((k+1)+1)((k+1)+2)=3(k+1)(k+2)(k+3). Inductive Step:
0⋅1+1⋅2+2⋅3+⋯+k(k+1)+(k+1)(k+2)=3k(k+1)(k+2)+(k+1)(k+2)=3k(k+1)(k+2)+33(k+1)(k+2)=3k(k+1)(k+2)+3(k+1)(k+2)=3(k+1)(k+2)(k+3)factor out (k+1)(k+2)