1
Q
What is the first thing you write down when doing induction?
A
Basis step, inductive step
2
Q
What do you do in the basis step?
A
Show P(1) is true
3
Q
What do you do in the inductive step?
A
Show P(k)→P(k+1) is true for all positive integers k
4
Q
What is the basis step proving that for all positive integers n, it holds that n < 2ⁿ?
A
P(1) is true since 1 < 2¹ = 2
5
Q
What is the inductive step proving that for all positive integers n, it holds that n < 2ⁿ?
A
Assume P(k) holds, k < 2ᵏ for an arbitrary positive integer k.
We show P(k+1) = k+1<2ᵏ⁺¹
By induction hypothesis, k<2ᵏ
Thus, k+1 < 2ᵏ+1 < 2ᵏ+2ᵏ = 2x2ᵏ = 2ᵏ⁺¹
This concludes the inductive step
6
Q
What is ∑ᵏ⁺¹ᵢ₌₁ equal to by definition of summation?
A
∑ᵏ⁺¹ᵢ₌₁ = ∑ᵏ ᵢ₌₁ i + (k+1)
Discrete Maths
flashcards
Decks in class (10)
# Cards
