Discrete Mathematics Project: Fibonacci Sequence & Pascal's Triangle

This Discrete Math project explores the relationship between the Fibonacci sequence and Pascal's Triangle. It begins by demonstrating the connection, where the Fibonacci sequence terms are shown to be the sum of the diagonals of Pascal's triangle. The project expands both sides of an equation related to the Fibonacci sequence up to n=10 and includes a program (in Maple) for both the left-hand side (LHS) and right-hand side (RHS). The results of the LHS and RHS are compared for n=100, and the project calculates the difference between the two sides using a Python program. Furthermore, the project provides a combinatorial proof of a binomial identity and demonstrates that the ratio of (Fn + 1) / Fn approaches the Golden Ratio. The project concludes with a list of references.

Running head: DISCRETE MATHS PROJECT 1
Discrete Math Project
By (Name of Student)
(Institutional Affiliation)
(Date of Submission)

DISCRETE MATHS PROJECT 2
Show that the Fibonacci sequence {fn} is related to Pascal Triangle.
The n-th number in this sequence is the sum of the (n 1)-st and (n 2)-nd number, or, more
Formally, the Fibonacci sequence Fn, n = 0, 1 . . . is defined as;
F0 =0; F1 =1; Fn =Fn1 +Fn2, n2.
The terms where n−k<kn−k<k are 00.
The Fibonacci sequence is related to Pascal's triangle in that the sum of the diagonals of Pascal's
triangle are equal to the corresponding Fibonacci sequence term.
Initial Values
For n=0n=0, the sum gives 11.
For n=1n=1, the sum gives 11.
By recursion
The recursion is satisfied:
∑k=0n(n−kk)+∑k=0n+1(n+1−kk)=∑k=1n+1(n+1−kk−1)+∑k=0n+1(n+1−kk)=1+∑k=1n+1(n+2
−kk)=∑k=0n+2(n+2−kk)(2)(3)(4)
Hence Fibonacci sequence {fn} is related to Pascal Triangle which is
Part a) Expand both sides up n=10
∀n∈Z>0:∀n∈Z>0:FnFn==∑k=0⌊n−12⌋(n−k−1k)∑k= 0⌊n−12⌋(n−k−1k)==(n−10)+(n−21)+(n−32)+⋯+(n
−jj−1)+(n−j−1j)(n−10)+(n−21)+(n−32)+⋯+(n−jj−1)+(n−j−1j) where j=⌊n−12⌋j=⌊n−12⌋

DISCRETE MATHS PROJECT 3
Part b) Write a program for the LHS and RHS (you can choose any programming language)
> assume(k,odd): interface(showassumed=0):
> lhSide:=Sum(binomial(k-j+1,k-2*j+1),j=0..1+(k-1)/2);
> value(%);
> simplify(expand(%));
> lhSide_final := %:
> rhSide:=Sum(binomial(k-j,k-2*j),j=0..1+(k-3)/2)+Sum(binomial(k-j-1,k-2*j-1),j=0..1+(k-
3)/2);
> simplify(expand(%));
> rhSide_final := %:
> is(lhSide_final=rhSide_final);
Part c) Compare the LHS and RHS result for n=100 using the program in part b
Using the program, the LHS and RHS result for n=100 is given as;
def fib(100):
SQRT5 = math.sqrt(5)
PHI = (SQRT5 + 1) / 2
return int(PHI ** n / SQRT5 + 0.5)

DISCRETE MATHS PROJECT 4
The result is 2.434, which is the difference between the LHS and RHS result for n=100
Part d) Prove the identity using either mathematical induction or a combinatorial proof
C(n,m) C(m,k) = C(n,k) C(n-k, m-k)
To give a combinatorial proof of this binomial identity, we need to find a counting problem for
which one side or the other is the answer and then find another way to do the count. Let S be a
set with n elements. The number of these ordered pairs is, C (n,m) C(m,k) using the product
rule and first counting the number of choices for M and then the number of choices for K. Now
we count the ordered pairs in a different way. First choose a K, this can be done in C (n,k)
ways, and next count the number of M's that contain this K. Since we must add m-k elements
to K to get an M, and these are in the complement of K, of size n-k, we have C (n-k,m-k) ways
to do this. So, C (n,m) C(m,k) = C(n,k) C(n-k, m-k) since these represent two ways to count
the same thing.
Part e) Show that (Fn + 1) / Fn =
Solution
The Golden Ratio proof
In calculating the ratio of two successive Fibonacci numbers, uunn+1, we
find that as n increases without bound, the ratio approaches .
Since

DISCRETE MATHS PROJECT 5
un+1 = un + un−1,
Then by definition, it follows that
.
Now, we let
We then see that
.
We now have the statement
,
which is equivalent to the equation;
.
This equation can then be rewritten as
L2 − L − 1 = 0,
Which is easily solved using the quadratic formula. By using the quadratic
formula, we have
.
Thus, we arrive at our desired result of

DISCRETE MATHS PROJECT 6
.
References
Falcon, S., & Plaza, A. (2009). Binomial transforms of the k-Fibonacci sequence. International
Journal of Nonlinear Sciences and Numerical Simulation, 10(11-12), 1527-1538.
Falcón, S., & Plaza, Á. (2017). The k-Fibonacci sequence and the Pascal 2-triangle. Chaos,
Solitons & Fractals, 33(1), 38-49.
Gould, H. W. (2009). The Girard-Waring power sum formulas for symmetric functions, and
Fibonacci sequences. Fibonacci Quarterly, 37, 135-140.
Hoggatt Jr, V. E. (2017). Fibonacci numbers and generalized binomial coefficients. Fibonacci
Quart, 5, 383-400.
Hosoya, H. (2008). Pascal’s triangle, non‐adjacent numbers, and D-dimensional atomic
orbitals. Journal of mathematical chemistry, 23(1-2), 169-178.

DISCRETE MATHS PROJECT 7
Walton, J. E., & Horadam, A. F. (2014). Some aspects of generalized Fibonacci numbers. The
Fibonacci Quarterly, 12(3), 241-250.