Week 6 - Recurrences and Methods of Proof

Question 1

How is the fibonnaci sequence defined?

Answer 1

F_{n} = F_{n-1} + F_{n-2}

Question 2

What is a closed form formula?

Answer 2

Being able to find the “nth” term in a sequence based on a formula.

Question 3

F(n-1)*F(n+1) = ?

Answer 3

F(n^2) + (-1)^n

take 3 sequences of fibonnacci, take the two outer ones, multiply them, and you get the middle one squared by either adding or substracting 1

Question 4

8. an = an-1 + d is an ____, it also has constant differences

Answer 4

arithmetic sequence

Question 5

9. an = r * an-1 is a ____

Answer 5

geometric sequence

Question 6

12. A homogeneous recurrence relation what is it?

Answer 6

12. A homogeneous recurrence relation is one that evaluates to 0 when 0 is plugged into the a(j) side on the right hand side
    a. Homogeneous means same (LS = RS)

Question 7

15. An arithmetic sequence is a sequence with the difference between two consecutive terms _____. The difference is called the common difference. A geometric sequence is a sequence with the ____ between two consecutive terms constant.

Answer 7

constant, ratio

Question 8

The Golden Ratio

Answer 8

i. Let a and b be two positive numbers such that a

Question 9

How to find a close form solution?

Answer 9

a. Look at the information/variables you’re given and figure it out (i.e. subscripts, sample values or sequences)
b. Look at differences (first, second, third) which gives you linear, quadratic or polynomial if it’s a constant difference
i. Create a set of equations and keep reducing equations until you have 2 that you can subtract
ii. Then check that it works for your values (or do a proof by induction)