Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Title: Examples of principle of mathematical induction(P.M.I)
Description: a well modified solved understanding examples of principle of mathematical induction(P.M.I)
Description: a well modified solved understanding examples of principle of mathematical induction(P.M.I)
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
Induction Examples
Question 1
...
2
Solution
...
The statement P1 says that
1=
n(3n − 1)
...
Inductive Step
...
2
It remains to show that Pk+1 holds, that is,
1 + 4 + 7 + · · · + (3(k + 1) − 2) =
Therefore Pk+1
(k + 1)(3(k + 1) − 1)
...
2
holds
...
Induction Examples
Question 2
...
Solution
...
Base Case
...
Inductive Step
...
It remains to show that Pk+1 holds, that is, that 6k+1 − 1 is divisible by 5
...
By Pk , the first term 6(6k − 1) is divisible by 5, the second term is clearly divisible by 5
...
Therefore Pk+1 holds
...
Induction Examples
Question 3
...
For any integer n ≥ 1, let Pn be the statement that
12 + 22 + 32 + · · · + (2n)2 =
n(2n + 1)(4n + 1)
...
The statement P1 says that
12 + 22 =
(1)(2(1) + 1)(4(1) + 1)
3(5)
=
= 5,
3
3
which is true
...
Fix k ≥ 1, and suppose that Pk holds, that is,
12 + 22 + 32 + · · · + (2k)2 =
k(2k + 1)(4k + 1)
...
3
12 + 22 + 32 + · · · + (2(k + 1))2 = 12 + 22 + 32 + · · · + (2k + 2)2
= 12 + 22 + 32 + · · · + (2k)2 + (2k + 1)2 + (2k + 2)2
k(2k + 1)(4k + 1)
=
+ (2k + 1)2 + (2k + 2)2
3
k(2k + 1)(4k + 1) 3(2k + 1)2 + 3(2k + 2)2
=
+
3
3
k(2k + 1)(4k + 1) + 3(2k + 1)2 + 3(2k + 2)2
=
3
2
k(8k + 6k + 1) + 3(4k 2 + 4k + 1) + 3(4k 2 + 8k + 4)
=
3
(8k 3 + 6k 2 + k) + (12k 2 + 12k + 3) + (12k 2 + 24k + 12)
=
3
8k 3 + 30k 2 + 37k + 15
=
3
On the other side of Pk+1 ,
(k + 1)(2k + 2 + 1)(4k + 4 + 1)
(k + 1)(2(k + 1) + 1)(4(k + 1) + 1)
=
3
3
(by Pk )
Induction Examples
(k + 1)(2k + 3)(4k + 5)
3
2
(2k + 5k + 3)(4k + 5)
=
3
8k 3 + 30k 2 + 37k + 15
=
...
Thus, by the principle of mathematical induction, for all n ≥ 1, Pn holds
...
Consider the sequence of real numbers defined by the relations
√
x1 = 1 and xn+1 = 1 + 2xn for n ≥ 1
...
Solution
...
Base Case
...
Inductive Step
...
It remains to show that Pk+1 holds, that is, that xk+1 < 4
...
Therefore Pk+1 holds
...
Induction Examples
Question 5
...
Solution
...
Base Case
...
Inductive Step
...
It remains to show that Pk+1 holds, that is, that (k + 1)! > 3k+1
...
Therefore Pk+1 holds
...
Induction Examples
Question 6
...
Use
an extended Principle of Mathematical Induction to prove that pn = cos(nθ) for n ≥ 0
...
For any n ≥ 0, let Pn be the statement that pn = cos(nθ)
...
The statement P0 says that p0 = 1 = cos(0θ) = 1, which is true
...
Inductive Step
...
It remains to show that Pk+2 holds, that is, that pk+2 = cos((k + 2)θ)
...
Therefore,
pk+2 = 2p1 pk+1 − pk
= 2(cos θ)(cos((k + 1)θ)) − cos(kθ)
= (cos θ)(cos((k + 1)θ)) + (cos θ)(cos((k + 1)θ)) − cos(kθ)
= cos(θ + (k + 1)θ) + sin θ sin(k + 1)θ + (cos θ)(cos((k + 1)θ)) − cos(kθ)
= cos((k + 2)θ) + sin θ sin(k + 1)θ + (cos θ)(cos((k + 1)θ)) − cos(kθ)
= cos((k + 2)θ) + sin θ sin(k + 1)θ + cos((k + 1)θ − θ) − sin(k + 1)θ sin θ − cos(kθ)
= cos((k + 2)θ) + cos(kθ) − cos(kθ)
= cos((k + 2)θ)
...
Thus by the principle of mathematical induction, for all n ≥ 1, Pn holds
...
Consider the famous Fibonacci sequence {xn }∞
n=1 , defined by the relations x1 = 1, x2 = 1,
and xn = xn−1 + xn−2 for n ≥ 3
...
(b) Use an extended Principle of Mathematical Induction in order to show that for n ≥ 1,
[(
√ )n (
√ )n ]
1
1+ 5
1− 5
−
...
Solution
...
2
2
5
Base Case
...
The statement P2 says that
(
√ )2
√ )2 (
1− 5
1
1+ 5
−
x2 = √
2
2
5
Induction Examples
) (
)]
√
√
1+2 5+5
1−2 5+5
−
4
4
[(
)]
√
√
1
1+2 5+5−1+2 5−5
=√
4
5
[ √ ]
1 4 5
=√
4
5
1
=√
5
[(
= 1,
which is again true
...
Fix k ≥ 1, and suppose that Pk and Pk+1 both hold, that is,
(
√ )k (
√ )k
1
1+ 5
1− 5
xk = √
−
,
2
2
5
(
and
xk+1
√ )k+1 (
√ )k+1
1+ 5
1
1− 5
...
xk+2 = √
−
2
2
5
xk+2 = xk + xk+1
(
(
√ )k (
√ )k+1 (
√ )k
√ )k+1
1
1+ 5
1− 5
1
1+ 5
1− 5
=√
−
+√
−
2
2
2
2
5
5
(
√ )k (
√ )k+1 (
√ )k (
√ )k+1
1+ 5
1+ 5
1− 5
1− 5
1
+
−
−
=√
2
2
2
2
5
(
√ )k (
√ ) (
√ )k (
√ )
1
1+ 5
1+ 5
1− 5
1− 5
=√
1+
−
1+
2
2
2
2
5
(
√ )k (
√ ) (
√ )k (
√ )
1 1+ 5
3+ 5
1− 5
3− 5
=√
−
2
2
2
2
5
(
√ )k (
√ ) (
√ )k (
√ )
1
1+ 5
6+2 5
1− 5
6−2 5
=√
−
2
4
2
4
5
Induction Examples
(
) (
)
√ )k (
√
√ )k (
√
1
1+ 5
1+2 5+5
1− 5
1−2 5+5
=√
−
2
4
2
4
5
(
√ )k (
√ )2 (
√ )k (
√ )2
1
1+ 5
1+ 5
1− 5
1− 5
−
=√
2
2
2
2
5
(
√ )k+2 (
√ )k+2
1
1− 5
1+ 5
...
Thus by the principle of mathematical induction, for all n ≥ 1, Pn holds
...
Title: Examples of principle of mathematical induction(P.M.I)
Description: a well modified solved understanding examples of principle of mathematical induction(P.M.I)
Description: a well modified solved understanding examples of principle of mathematical induction(P.M.I)