Key Concepts in Computer Science -Assignment 10

1) [8 marks] Prove using mathematical induction that 3 + (3×5) + (3×52) + … + (3×5n) = (3×(5n+1 – 1))/4 whenever n is a nonnegative integer.
Let P(n) be the following proposition:

2) [12 marks]
a) Find a formula for
1/2+1/4+1/8+⋯+1/2^𝑛
by examining the values of this expression for small values of n.
Ans: Let’s compute the values of this sum for n :S 4 to see whether we can discover a pattern. For n = 1 the sum is 1/2. For n = 2, the sum is 3/4, for n = 3, the sum is 7/8 and for n=4, the sum is 15/16. Thus, the pattern clearly is (2n -1)/2n .
b) Prove using mathematical induction the formula you conjectured in part (a).
Ans: We have already verified that this is true in the base case (in fact, in four base cases). So let us assume it for k and try to prove it for k + 1. More formally, we are letting P(n) be the statement that

the right-hand side of P(k + 1).
4) [10 marks] Which amounts of money can be formed using just two-dollar bills and five-dollar bills? Prove your answer using strong induction.
Ans: We can form the following amounts of money as indicated: 2 = 2, 4 = 2 + 2, 5 = 5, 6 = 2 + 2 + 2. By having considered all the combinations, we know that the gaps in this list ($1 and $3) cannot be filled. We claim that we can form all amounts of money greater than or equal to 5 dollars. Let P(n) be the statement that we can form n dollars using just 2-dollar and 5-dollar bills. We want to prove that P(n) is true for all n ≥ 5. We already observed that the basis step is true for n = 5 and 6. Assume the inductive hypothesis, that P(j) is true for all j with 5 ≤ j ≤ k, where k is a fixed integer greater than or equal to 6. We want to show that P(k + 1) is true. Because k – 1 ≥ 5, we know that P(k – 1) is true, that is, that we can form k – 1 dollars. Add another 2-dollar bill, and we have formed k + 1 dollars, as desired.
5) [10 marks] Find f (2), f (3), and f (4) if f is defined recursively by f (0) = −1, f (1) = 2, and for n = 1, 2, . . .
a) f (n + 1) = f (n) + 3f (n − 1)
 f(2) = f(l) + 3f(0) = 2 + 3(-1) = -1
 f(3) = f(2) + 3f(l) = -1 + 3·2 = 5
 f(4) = J(3) + 3f(2) = 5 + 3(-1)=2
b) f (n + 1) = ( f (n)2 )×( f (n − 1) )
 f(2) = f(1)2f(0) = 22·(-1) = -4
 f(3) = f(2)2f(l) = (-4)2·2 = 32
 f(4) = f(3)2f(2) = 322·(-4) = -4096
6) [10 marks] Assume fn is the nth Fibonacci number. Prove using mathematical induction that f1 + f3 + · · · + f2n−1 = f2n when n is a positive integer.
Ans: We prove this using the principle of mathematical induction. The base case is n = 1, and in that case the statement to be proved is just f1 = f2; this is true since both values are
1. Next we assume the inductive hypothesis, that