[Solved] ICSI403-Homework 2

1. Given below are several pairs of functions f(n) and g(n). For each pair, . Show work. For some of these, you may need to use LHospitals rule.

• f(n) = 15n² and g(n) = 5. (b) f(n) = 2ⁿ and g(n) = n².

(c) f(n) = n ln n and g(n) = 17n² + 4. (Note that ln denotes the natural logarithm.) (d) f(n) = 3ⁿ and g(n) = 2ⁿ.

2. (a) Use induction on n to prove that for all integers n >= 0, the value 4ⁿ + 1 is not divisible by 3.

• Consider the infinite sequence of integers f₀, f₁, f₂, , defined by f₀ = 1, f₁ = 2 and

f_n = f_n-1 + f_n-2 for all n >= 2. Use induction on n to prove that for all n >= 1.

3. Let A = {x; y; z; w} and let B = {1; 2; 3}. Determine the number of functions from A to B that are neither one-to-one nor map y to 3. Show work. (20 points) Hint: Use the principle of inclusion-exclusion.

4. Let A = {x₁; x₂; ; x₁₀} be a set of 10 positive integers, not necessarily distinct, such that x_i <= 10, 1 <= i <= 10. Prove that there are at least two different 5-element subsets S₁ and S₂ of A such that the sum of the elements in S₁ is equal to the sum of the elements in S₂.