Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

AMS 301 Homework #5

Due Date: 11:59pm, 12/11/2023

There are 10 problems. Each is worth 10 points for trying. Type up solutions to the first 2 problems.

1. a) Build a generating function for a_r, the number of integer solutions to the equation

e₁ + e₂ + e₃ + e₄ + e₅ = r, 0 ≤ e_i ≤ 4. Completely explain your answer.

b) Build a generating function to count the number of integer solutions to the equation

1 + x + x² + x³ + x⁴ = 32 where x₁ and x₂ ≥ 5 and x₃ and x₄ ≥ 7. Explain how to get the answer.

2. a) Find the coefficient of x⁸ in (x² + x³ + x⁴)³.

b) Find the coefficient of x¹⁰ in (1 + x⁵ + x¹⁰ + x¹⁵  + ….)³.

3. Use generating functions to find the number of ways to make change for $100 using the given constraint. Make sure to explain the answer using generating functions.

a) Using $10, $20 and $50 dollar bills.

b) Using $5, $10, $20 and $50 dollar bills;

c) Using $5, $10, $20 and $50 dollar bills and at least one bill of each denomination is used.

4. a) Find a recurrence relation for the number of bit strings of length n that do not contain three consecutive 0's.

b) What are the initial conditions?

c) How many bit strings of length 7 do not contain three consecutive 0's?

5. Solve the following recurrence relations.

a) a_n = 2a_n-1 - a_n-2, a₀ = a₁ = 2

b) a_n = 5a_n-1 - 6a_n-2 + 7ⁿ, 

6. Solve the following recurrence relations.

a) a_n = 5a_n-1 - 6a_n-2, a₀ = 1, a₁ = 0

b) a_n = a_n-1, a₀ = 2 

7. Consider the recurrence relation for the number of regions created by n mutually overlapping circles on a piece of paper (no three circles have a common intersection point).

a) Give the results for n = 2, 3 and 4 by drawing the correct picture.

b) Find the recurrence relation for the number.

c) Find the number when n = 12.

8. Prove by induction that 1² + 3² + … + (2n-1)² =

9. Prove by induction that the sum of the cubes of three successive positive integers is divisible by 9.

10. For the following Fibonacci identities verify that the identity is true for n = 1, 2, 3 and 4. Then verify the following identities for Fibonacci numbers by induction.

a) f₀ + f₁ + … + f_n = f_n+2 − 1

b)  f₁ + f₃ + … + f_2n-1= f_2n