Loading...
Discussion 1A
Induction
Prove that for all
n
∈
N
n \in \mathbb{N}
n
∈
N
,
P
(
n
)
P(n)
P
(
n
)
holds.
Weak induction steps:
Base case:
Prove that
P
(
0
)
P(0)
P
(
0
)
holds
Inductive hypothesis
: Assume that
P
(
k
)
P(k)
P
(
k
)
holds for some value of
k
k
k
Inductive step
: Show that
P
(
k
+
1
)
P(k+1)
P
(
k
+
1
)
holds under the inductive hypothesis
Strong induction steps:
Base case
: Prove that
P
(
0
)
P(0)
P
(
0
)
holds
Inductive hypothesis
: Assume that
P
(
n
)
P(n)
P
(
n
)
holds for all values of
n
n
n
between
0
0
0
and
k
k
k
Inductive step
: Show that
P
(
k
+
1
)
P(k+1)
P
(
k
+
1
)
holds under the inductive hypothesis
Applications
Divide and conquer/recursion problems
Binary search, sorting
Graphs
Trees
minor typo on 1b:
1
2
+
2
2
+
3
2
+
⋯
1^2 + 2^2 + 3^2 + \cdots
1
2
+
2
2
+
3
2
+
⋯
Please turn on JavaScript to use Paper in all of its awesomeness. ^_^
Induction
Weak induction steps:
Strong induction steps:
Applications