Project 2 Recursion

  • The binomial coefficients C(n,k)are defined recursively as follows:
    1. C(n,k)=C(n-1,k)+C(n-1,k-1) for all integers n,k>0
    2. C(n,0)=1 for all integers n\geq 0
    3. C(0,k)=0 for all integers k>0
  • Plot the central binomial coefficient C(2n,n) as a function of n for 0\leq n \leq 25
  • Find upper bounds for, or determine, the rate of growth of C(2n,n) as a function of n.

A.) To obtain the following function in Mathematica I plugged in the following code section. The following graphs are also a great visual representation.

REDDOT[n_, k_] :=
REDDOT[n, k] = ReleaseHold[REDDOT[n – 1, k] + REDDOT[n – 1, k – 1]];

REDDOT[n_, 0] = 1;

REDDOT[0, k_] = 0;

T = Table[{n, REDDOT[(2*n), n]}, {n, 0, 25}];

ListPlot[T]
ListLogPlot[T]

(Click To make Bigger)

The upper bounds of C(2n,n) as a function of n can be calculated using the Stirling’s Formula. Developed by James Stirling, this formula gives an approximation for large factorials. The simple lower and upper bounds are given by:
\frac{4^n}{n+1} \le \binom{2n}{n} \le 4^n. More accurate bounds are given by: \frac{4^n}{\sqrt{4n}} \le \binom{2n}{n} \le \frac{4^n}{\sqrt{3n+1}} . In Big-Oh notation, the upper bound 4^n is a polynomial 0(n^c), c > 1 = 0(4^c), c > 1.  The upper bounds of this graph give us all the information we need to know as we can calculate any values needed.

I also used mathematics fit function in order to obtain another possible option. The code follows this excerpt.

Fit[T, {0, n}, n]

= 0.+ 7.57432*10^11 n

B.)

WALK THE GRID

Imagine walking on the grid below, from the red dot (the “origin”) to any other dot by walking UP one step or RIGHT one step at a time:

  • Show that the number of different paths from the origin to a dot that is k steps UP and n-k steps RIGHT (or vice versa), where k \le n is C(n,k)
  • For the dots that are 15 steps away from the origin calculate how many different paths there are to that dot.
  • Use Mathematica to expand (a+b)^{15} and examine the coefficients of the powers a^{n-k}b^k. Is this a coincidence?

Taking only one step in the upward or rightward direction when trying to maneuver your way through this maze can be looked at as pascals triangle. To show what I mean by this I have attached a picture to show the process.

This image was taken from wikipedia. It explains perfectly how walking through this grid would occur. You simply add the numbers of the 2 adjacent honeycombs and it subsequently gives you the answer to the following spot.

http://tejendrapatelmth350.files.wordpress.com/2012/10/numofpaths.png

The above table taken from a google image shows us exactly what our value would be at row (15,15) which is 40116600.

In expanding we get the following equation

This equation shows that no matter what the values for a or b are they will always add up to 15. There is also nothing special about 15 as you can do this with any number in mathematica and recieve very similar results.

BLOCKS

A block tower of 2 colors is built as a vertical stack of blocks, with a bottom and a top. Below are several block towers of height 5:

    • How many block towers of height 5 are there and what are they?
    • What does this have to do with the binomial expansion of (a+b)^5 ?
    • What does it have to do with the number of walks on the grid, above, to points that are 5 steps from the origin?
    • What connection is there between block towers of height n, the binomial expansion of (a+b)^n and walks on the grid to points that are n steps from the origin?

When first looking at this problem I didn’t know how to approach it but after reevaluating it  I realized after expanding  (a+b)^{5} = a^{5} + 5 a^{4} b + 10 a^{3} b^{2} + 10 a^{2} b^{3} + 5 a b^{4} + b^{5} That there could be 32 different combinations according to the expansion. This is derived by taking the fact that there is two possible states for each block. A block can either be black or white. When there is one block the formula gives you two states, which is correct. When there are two blocks, the formula will give you four possible states.

EX.) 2^N= Number of combinations, Where N = number of blocks ; 2^(5)= 32

Dijkstra’s fusc function

We define the function fusc(n) and plot it as the following image will show.

for values known as  0 \le n \le 10,000

the following code gave me the values for n<100

fusc[n_]:=If[EvenQ[n]==True,fusc[n/2],fusc[(n-1)/2]+fusc[(n+1)/2]];

fusc[0]:=0;

fusc[1]:=1;

t1=SessionTime[];

A=Table[{n,fusc[n]},{n,0,99}];

Grid[A]

Image

For every value of n that is a multiple of 3, the table says true if fusc(n) is even. The table shows that this is true for every multiple of three.

For proof by induction i have used a couple different fusc functions below making sure to walk through every step in order to show that through induction each is true. For the example I will be using fusc(6) but to find fusc(6) you must first find fusc(3)

fusc[3] = fusc[(3-1)/2] + fusc[(3+1)/2] = fusc[1] + fusc[2] = 1 + 1 = 2

fusc[6] = fusc[6/2] = fusc[3] = 2

Since the two outputs have the same number it shows that the fusc function is correct and that for every value of n that is a multple of 3 the fusc n will be even.

For proof that fusc[n] is not a multiple 2 when n is not a multiple of 3 please follow the next proof by induction.

fusc[4] = fusc[4/2] = fusc[2] = fusc[2/2] = fusc[1] = 1

fusc[7] = fusc[(7-1)/2] + fusc[(7+1)/2] = fusc[3] + fusc[4] = 2 + 1 = 3

The previous examples show how

Fibonacci numbers

The fibonacci numbers  f(n) are determined by the following recursive relation:

F(0)=1=F(1); F(n)=F(n-1)+F(n-2) \textrm{ for } n\geq 2

Use Mathematica to calculate and plot F(n) \textrm{ for } 0\leq n \leq 50

(Click to make bigger)

(Click to make bigger)

The growth rate is growing exponentially, so f(n) will increase proportionally to n so that means they will have the same growth rate.

The above code and graph were produced using mathmatica given to find the growth rate. Via the graph 1.61803 is the b term in our a*b^n Formula. Using the log function to find a slope that matches one of the graphs we find out that the growth rate of the graph is approximately 1.58.

An example of the growth rate of Fn there is a chart below that describes the situation a lot better and gives an example of how the growth rate is increasing in our case.

Screen Shot 2012-12-14 at 3.59.28 PM

Generating Primes

The graph below shows Computation of dp(n) or the number of distinct primes generated as g(n):=a(n)-a(n-1), n>1 along with the graph of dp(n) as a function of n:

As we can tell from the graph dp(n) is always increasing as n becomes bigger. With this in mind we can also say that it is getting slower and slower the further we go through the graph therefor it is increasing at a slow rate.  For example just in order to get a distinct 11 prime numbers it would take a value of n to be  close to 960 . The function is not one-to-one because it has the same value for dp(n) for multiple values of n. It also appears to be increasing exponentially as a lot of the graphs in this project have been.

Leave a comment