Quiz 7
Discrete Mathematics · 1 problem · solutions hidden, click to reveal
Flashcards
Problems
Let \(f\) be defined by \(f(0) = 0\) and \(f(n) = f(n-1) + 2n - 1\) for \(n \ge 1\).
(1) Find \(f(1), f(2), f(3), f(4)\).
(2) Conjecture a formula for \(f(n)\).
(3) Prove your formula by induction.
(1) Find \(f(1), f(2), f(3), f(4)\).
(2) Conjecture a formula for \(f(n)\).
(3) Prove your formula by induction.
Show solution
Answer: \(f(1)=1,\ f(2)=4,\ f(3)=9,\ f(4)=16\); conjecture \(f(n) = n^2\).
(1) \(f(1)=1,\ f(2)=4,\ f(3)=9,\ f(4)=16\).
(2) Conjecture \(f(n) = n^2\).
(3) Let \(P(n): f(n) = n^2\). Base: \(f(0) = 0 = 0^2\). Step: assume \(f(k) = k^2\). Then
\(f(k+1) = f(k) + 2(k+1) - 1 = k^2 + 2k + 1 = (k+1)^2.\)
By induction, \(f(n) = n^2\) for all \(n \ge 0\).
(2) Conjecture \(f(n) = n^2\).
(3) Let \(P(n): f(n) = n^2\). Base: \(f(0) = 0 = 0^2\). Step: assume \(f(k) = k^2\). Then
\(f(k+1) = f(k) + 2(k+1) - 1 = k^2 + 2k + 1 = (k+1)^2.\)
By induction, \(f(n) = n^2\) for all \(n \ge 0\).