CS 173 Study Guide - Final Guide: Natural Number, New Zealand

• School: University of Illinois
• Department: Computer Science
• Course: CS 173
• Professor: All

Document Summary

6 (20 points) use (strong) induction to prove that a b divides an bn, for any integers a and b and any natural number n. Hint: (an bn)(a + b) = (an+1 bn+1) + ab(an 1 bn 1), for any real numbers a and b. Use (strong) induction to prove that f (n, a) = n! a!(n a)! for any natural numbers a and n, where n a. At each step, make sure the equations work for an arbitrary natural number a n. Rest of the inductive step: [first deal with two special cases: f (k, 0) and f (k, k). ] Use (strong) induction to prove that f (n) = 1 2n + 2 3n. 6 (20 points) suppose that f : n n is de ned by f (0) = 0 f (1) = 1 f (n) = f (n 1) + f (n 2) for all n 2.