Discrete Mathematics for Computer Scientists -- Assignment 3 - InductionDIT980, HT 2015
Home | Schedule | Assignments | Exercises | Exam | AboutFire | Forum | TimeEdit | Links | 2014
Assignment Week 3 - Induction

Please submit using the Fire system

Assignments

 (1.) Show that n3 ≤ 3n, for all n ≥ 0. Hint: Show the cases n=0, n=1, n=2 separately first, and then prove it for n ≥ 3 by induction.

(2.) Consider the following recursively defined function F : ℕ -> ℕ:

 F(0) = 1 n-1 F(n) = ∑ F(i)     , for n ≥ 1 i=0

In other words, F(n) for n ≥ 1 is defined as the sum of all previous values of F.

(a.) Show the values of F(0),F(1),F(2),F(3),F(4),F(5) and how to compute them using the definition above.

(b.) For which of the F(0),...,F(5) do we have that F(n) = 2n-1?

(c.) Prove by induction over n that F(n) = 2n-1 for n ≥ 1.

Submission

Submission of this assignment should be done electronically through the Fire system.

The submission deadline is Wednesday, September 23, at 13:00. At this time, you should have submitted a serious attempt to solve the assignment. A serious attempt is either an answer you believe to be correct, or a partial answer plus a detailed explanation of what you have tried to come up with a full answer. An empty document is not a serious attempt.

After submitting, you have until October 5 (midnight) to submit a completely correct version.