Fibonacci Numbers/Recurrences

Fibonacci Numbers: 

The Fibonacci Numbers are named after Leonardo Fibonacci. Fibonacci numbers are closely related to Lucas numbers, but I am going to be talking more about the Fibonacci numbers. 

The Fibonacci Numbers are the numbers of this sequence 

The first two numbers in the Fibonacci sequence are 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subset number is the sum of the previous two.  

Example: Find the next number of the Fibonacci sequence. 

• The two is found by adding the two previous numbers before it ( 1+1) 
• The three is found by adding the two pervious numbers (1+2)
• And the five is (2+3) 
• And so on 

What is the next number of the sequence after 144?

Well if we add (89+144) we get 233. 

What is the next number of the sequence after 233?

The answer should be 377.

The first twenty one Fibonacci F_n for n = 0,1,2,....,20 are: 

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15	F16	F17	F18	F19	F20
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181	6765

which is defined by the recurrence relation 

Example: Using the recurrence relation find the next number from the picture below?

Find the next number using the recurrence relation?

Your answer should be 17711

                                                        Recurrence:

Example: Suppose I have a recurrence, defined by initial conditions 

 and  

 where 

we have the recurrence 

Using this formula we can generate the next a numbers ( which i am not going to do, but you may do it, by plugging in 3 for n, and 4 for n, and so on.) 

Now we need to find a polynomial from the given equation. So we get the polynomial 

and this can be factored into: 

For the roots of the polynomial we will change both signs of the factored polynomial so root one =3 and root two =-2. Therefor for all n greater than or equal to 0, we get 

We need to make sure the recurrence works so we need to figure out what the constants are. When n=0 we get the equation

and when n=1 we get the equation

Now that we have two equations we can use the elimination method or the substitution method to figure out what c one and c two is. So by doing either methods we will get 

Now we put it all together to get our closed form recurrence: 

Quiz Question:

Suppose I have a recurrence, defined by initial conditions

 and

 where 

we have the recurrence 

Find the roots, and constants and final equation?

Citations: 

wikepedia, mathURL, math is fun, discrete mathematics

Principle of Mathematical Proofs

                                                         Induction Proofs:

The Principle of mathematical proofs (PMI) is not an easy proof at first, these types of proofs take practice. To set up (PMI) we need to choose a

 Base Case: prove that  is true

Induction Step: suppose that  is true.

                                               Prove that  is also true. 

It is important that the structure of the proof is correct. In the induction step we are assuming 

 is true. We actually assume  is true for all k. 

Example:  Prove 1+2+3+.....+100=? For all n in N, 

Proof by PMI: 

Base Case: we must show 

LHS: (left hand side) 

RHS: (right hand side) 

Right hand side and left hand side =1 so the base case is true. 

Induction Step: Suppose that 

 we want to prove 

.

 by the inductive hypothesis

 which is what we wanted to prove. 

Thereforefor all n in N. 

It is sometimes easier to work out the first steps to get a sense of how to prove the general inductive step, like i did up above. 

Potential Exam Question: For all n greater than of equal to Z, Prove the following statement: 

Citations: Professor Aaron Wong Proof Notes / Professor Arthur T. Benjamin's Video notes

The Multinomial Coefficient

                                                        The Multinomial Coefficient 

Defining  it looks like

  

 but it has an extra set of parentheses around and  it is the number of ways to choose k         objects from a set of n objects, where order is not important, but repetition is allowed.

The equation is

Lets try a Couple of examples using this formula:

Example One: Find the number of solutions to the equation a + b + c = 40, where a, b, and c are all non-negative integers.

Example Two:  Suppose you have 15 ice cream flavors and you want a cup of five scoops, they can be the same flavor. How many ways can we choose the flavors?

Example Three:  How many ways can we arrange the letters Richelle?

Well we see that there are two L’s and two E’s one R, one I, one C and one H. So we can use the other equation, which introduces the multinomial coefficient, the equation is

There are eight letters in Richelle. So there are

 The Right arrow is point to the multinomial coefficient.

So the answer to how many ways we can arrange Richelle is

Example Four: How many ways can you arrange the letters in Halloween?

There is 1 H, 1 A, 2 L’s, 1 O, 1 W, 2 E’s and 1 N. in Halloween.

The Multinomial Theorem states:

Where a and b are non-negative numbers that sum up to n. We will use this theorem later.

Test Question: How many ways can you arrange the letters in Nevada State College, you can count them as all one word?

Test Question: Find the number of solutions to the equation a + b + c + d +e + f =150, where a,b,c.d.e and f are all non-negative integers?