Udemy | Introductory Programming Course | Math Prerequisite
Factorial, Fibonacci and Summation in Counting and Probability
Prerequisites for Programming and Algorithms
Factorial
It is a product of all positive integers less than or equal to n.
A factorial of n is n! = 1 x 2 x 3 x … x (n-2) x (n-1) x n
A factorial of 6 would be = 6! = 1 x 2 x 3 x 4 x 5 x 6 = 720
Factorials are widely used in permutations, combinations, and various areas of mathematics and computer science.
Fibonacci
It is a series of recurrence of numbers of this form.
F₀ = 0, F₁= 1, Fᵢ = F₍ᵢ₋₁₎ + F₍ᵢ₋₂₎ where i = {2, 3, …., n}
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Fibonacci numbers are related to the golden ratio ɸ and to its conjugate ɸ’ . These are the roots of the equation x² = x + 1. The image depicts the golden ratio created by Fibonacci numbers.
The values of the golden ratio and its conjugate can hence be calculated from this equation as
ɸ = (1 + √5)/2 and ɸ’ = (1 — √5)/2
Hence the iᵗʰ element in the Fibonacci series can be represented as
Fᵢ = (ɸⁱ + ɸ’ ⁱ)/√5
Summation ∑
It is the mathematical notation that indicates the addition of several numbers.
In algorithms it can express the running time of a for loop as the sum of the times spent in each execution of the body of the loop.
For a sequence of a₁, a₂, a₃, a₄,..aₙ numbers, where n is a nonnegative integer we can write the finite sum a₁+ a₂+ a₃+ a₄+...+aₙ as ∑ⁿₖ₌₁aₖ.
Arithmetic Series:
The summation of k = {1, 2, 3, 4, 5, …, n} is an arithmetic series
Sum of Squares: The summation of k² = {1, 4, 9…, n²} is
Sum Of Cubes: The summatio of k³ = {1,8,27,…n³} is
Geometric or Exponential Series:
If the series is of the form
Harmonic Series:
Harmonic Series looks like
This series diverges, meaning that its sum grows without a limit as more terms are added. However, the sum of the first (n) terms of the harmonic series, known as the nᵗʰ harmonic number (Hₙ), can be approximated by:
where ln(n) is the natural logarithm of n and γ is the Euler-Mascheroni constant, approximately equal to 0.5772112.
