Discrete Math Project

Prove the relationship between the Fibonacci sequence and Pascal's Triangle, expand both sides up to n=10, write a program to calculate the left-hand side (LHS) and right-hand side (RHS), compare the results for n=100, and prove the identity (Fn + 1) / Fn = Golden ratio.

7 Pages677 Words490 Views

Added on 2023-03-31

About This Document

This project explores the relationship between the Fibonacci sequence and Pascal's Triangle. It demonstrates that the Fibonacci sequence is related to Pascal's Triangle by showing that the sum of the diagonals of Pascal's Triangle are equal to the corresponding Fibonacci sequence term.

Discrete Math Project

Added on 2023-03-31

Related Documents

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)

End of preview

Want to access all the pages? Upload your documents or become a member.