1. Which amounts of money can be formed using just two-dollar bills and five-dol

Question

1. Which amounts of money can be formed using just two-dollar bills and five-dollar bills? Use strong induction. 2. Give a recursive definition of the set of positive integers that are multiples of 5. 3. Suppose f : N right arrow R is defined recursively as follows: Basis step: f (1) = 1 Recursive step: f(n + 1) = f(n) (2n + 1) for n greater than or equal to 1 Prove that f (n) = n^2 for all n greater than or equal to 1. 4. Suppose f : N U {O} right arrow R is defined recursively as follows: Basis step: f (0) = 1 and f(1) = 2 Recursive step: f(n + 1) = f (n) + 2f (n - 1) for n greater than or equal to 1 Prove that f (n) = 2^n for all n greater than or equal to 1. 5. Let fn be the nth Fibonacci number as defined in class. Prove that F1 + f2^2 + ? + fn^2 = fnfn+1

Explanation / Answer

1)

Compute rst a few integers by hands. If you want to use strong induction, pick the smaller
number between 2 and 5. To setup a basis step, it is the key that nding two consecutive integers that can
be paid by two-dollar and ve-dollar bills. Let's say
(n): n = 2x + 5y for some non-negative integers x; y
Check that (n) is true for n = 2; 4; 5; 6; 7; . So the statement we'll prove is:
(n) is true for all n 4
A basis step is (4) and (5). Indeed,
4 = 2 2; 5 = 5 1
Now assume (i) is true for all 4 i k for k 5. We'll prove that (k+1) is also true. Since k 5,
4 k ?? 1 < k and thus the inductive assumption says (k??1) is true. Now we only add 2 to the linear
combination of k ?? 1 = 2x + 5y with x; y 0 to get a desired linear combination for k + 1. To sum up, (n)
is true for n = 2 and n 4.

2)

We can define the set S={x|x is a pos. int. and x is a multiple of 5} by the base case requirement that 5

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.