Math 100, Winter 2022 Second Writing Assignment
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Math 100, Winter 2022 Second Writing Assignment
November 9, 2022
Abstract
This note contains your second assignment details.
1 Introduction
The goal of this writing assignment is to prove several theorems on the Fibonacci sequence of numbers, culminating in the Binet representation which expresses fn as a formula in n.
2 Instructions
Below are the detailed instructions.
1. Define what is meant by a sequence of numbers, {an }1(o) .
2. Define what it means for a sequence to be defined recursively. Give two examples other then the Fibonacci sequence
3. Define the Fibonacci sequence.
4. Write a brief history of the Fibonacci sequence (in your own words).
5. Prove at least two of the following:
5.1 Set F =『1(0) 1(1)← . Prove that Fn = ← .
5.2. Prove fn+1fn-1 - fn(2) = (-1)n holds for all n e ← .
5.3 Prove that fn(2) + fn(2)+1 = f2n+1 holds for all n e ← . Hint: F2n = Fn Fn .
5.4 Prove that f2 + f4 + . . . + f2n = f2n+1 - 1.
6. Prove at least one of the following.
6.1 Let sn be the number of ways of expressing n as a sum of one’s and two’s where the order counts; that is, 1 + 2 and 2 + 1 are considered different. Compute the first six values of sn and convince yourself that sn = fn+1 . Let n be a natural number and set h =「|. Prove when expressing n as a sum of one’s and two’s the number of ways to do so with k two’s, k < h and n - 2k ones is ╱n k(-)k、and conclude that
fn+1 = 『nk(-) k ← .
6.2 A subset U of {1, 2, . . . , n} is unfriendly if it does not contain any consecutive numbers, equivalently, if k < l are in U then l - k > 1. Denote by un the number of unfriendly subsets contained in {1, 2, . . . , n}? Note the empty set if unfriendly and needs to be counted. Compute the first six values of un and convince yourself that un = fn+1 . Prove this statement.
7. The Binet Formula for Fibonacci Numbers
7.1 Prove the following statement: If {gn } and {hn } satisfy g1 = h1 , g2 = h2 and gn+2 = Agn+1 + Bgn , hn+2 = Ahn+1 + Bhn then gn = hn for all natural numbers n.
7.2 Let {gn } and {hn } both satisfy the recursion equation Xn+2 = AXn+1 + BXn . Prove that the sequence {gn + hn } satisfies the recursion equation.
7.3 Assume the sequence {gn } satisfies the recursion equation Xn+2 = AXn+1 + BXn and c is a real number. Prove that the sequence {cgn } satisfies the recursion equation.
7.4 Assume {gn } and {hn } both satisfy the recursion equation Xn+2 = AXn+1 + BXn and c, d are real numbers. Prove that {cgn + dhn } satisfies the recursion equation.
7.5 Let r be a root of the quadratic equation X2 - AX - B = 0. Prove that the sequence {rn } satisfies the recursion equation Xn+2 = AXn+1 + BXn .
7.5 Assume the quadratic equation X2 - AX - B = 0, with B 0, has distinct roots, r1 and r2 . Prove if {gn } satisfies the recursion equation Xn+2 = AXn+1 + BXn there exists unique scalars c1 , c2 such that gn = c1r 1(n) + c2r2(n) .
7.5 Apply the above and determine scalars c1 , c2 such that fn = c1r 1(n) + c2r2(n) where r1 , r2 are the roots of the quadratic equation X2 - X - 1 = 0.
This expression for fn is known as the Binet formula.
2022-12-02