Discrete Math

1. Sequences

What is defined by sequences?

Sequences are ordered lists of elements. They are used to represent solutions to certain counting problems. They are also an important data structure in computer science. When the elements of an infinite set can be listed, the set is said to be countable.

Usually it is a function from a subset of the set of integers (either the set { 0, 1, 2, . . . } or the set { 1, 2, 3, . . . }) to a set S. A term of a sequence denoted by a_n is the image of the integer n.

	a₀ = 2 (-3)⁰ + 5⁰ = 2 ( 1 ) + 1 = 2 + 1 = 3
E.g.:	Determine the first six terms of a sequence { a_n } where a_n = 2 ( -3 )ⁿ + 5ⁿ
	a₁ = 2 (-3)¹ + 5¹ = 2 ( -3 ) + 5 = -6 + 5 = -1
	a₂ = 2 (-3)² + 5² = 2 ( 9 ) + 25 = 18 + 25 = 43
	a₃ = 2 (-3)³ + 5³ = 2 ( -27 ) + 125 = -54 + 125 = 71
	a₄ = 2 (-3)⁴ + 5⁴ = 2 ( 81 ) + 125 = 162 + 625 = 787
	a₅ = 2 (-3)⁵ + 5⁵ = 2 ( -243 ) + 3125 = -486 + 3125 = 2639
	The first six terms of the sequence are 3, -1, 43, 71, 787, 2639, . . .

A set of numbers arranged in a definite order according to some definite rule in which a function whose domain is the set N of natural numbers.

What are types of sequences?

1. Geometric Progression

Where a sequence is of a sequence of the form a, ar, ar², . . ., arⁿ where the initial term a and the common ratio r are real numbers.

E.g.:

Determine the first six terms of a geometric progression with initial term 6 and common ratio ¼ and where n starts with 0.
Recall that a geometric progression has the form arⁱ where i = 0, 1, 2, . . ., n.

ar⁰ = 6 ( ¼ )⁰ = 6 (1) = 6

ar¹ = 6 ( ¼ )¹ = 6 ( ¼ ) = 3 / 2

ar² = 6 ( ¼ )² = 6 ( 1 / 16 ) = 3 / 8

ar³ = 6 ( ¼ )³ = 6 ( 1 / 64 ) = 3 / 32

ar⁴ = 6 ( ¼ )⁴ = 6 ( 1 / 256 ) = 3 / 128

ar⁵ = 6 ( ¼ )⁵ = 6 ( 1 / 1024 ) = 3 / 512

The first six terms of the geometric progression are:

6	,	3 2	,	3 8	,	3 32	,	3 128	,	3 512	.

2. Arithmetic Progression

Where a sequence is of the form a, a + d, a + 2d, a + 3d, . . ., a = nd where the intial term a and the common difference d are real numbers.

	a + 0 * d = 7 + 0 * 5 = 7 + 0 = 7
E.g.:	Determine the first six terms of an arithmetic progression with initial term 7 and common difference 5. Recall that an arithmetic progression has the form a + i d where i = 0, 1, 2, . . ., n.
	a + 1 * d = 7 + 1 * 5 = 7 + 5 = 12
	a + 2 * d = 7 + 2 * 5 = 7 + 10 = 17
	a + 3 * d = 7 + 3 * 5 = 7 + 15 = 22
	a + 4 * d = 7 + 4 * 5 = 7 + 20 = 27
	a + 5 * d = 7 + 5 * 5 = 7 + 25 = 32
	The first six terms of the arithmetic progression are 7, 12, 17, 22, 27, 32.

3. Finite Sequence

A sequence in which the number of elements which are present in it is finite or countable is called the finite sequence. The total number of the elements which are present in the finite sequence is called the length of the finite sequence.

For example, 1, 2, 3, 4, ..........90 is the finite sequence as this is the list of some finite numbers.

4. Infinite Sequence

A type of sequence which is not a finite sequence is called infinite sequence.

For example, the sequence of successive quotients mentioned above is an infinite sequence. Infinite means "it never ends". Often, it is possible to express the rule, which yields the various terms of a sequence in terms of algebraic formula.

Consider for instance, the sequence of even natural numbers 2, 4, 6 …
Here, a₁ = 2 = 2 × 1, a₂ = 4 = 2 × 2, a₃ = 6 = 2 × 3, a₄ = 8 = 2 × 4 … a₂₄ = 48 = 2 × 24, and so on.

5. Fibonacci Sequence

In some cases, an arrangement of numbers such as 1, 1, 2, 3, 5, 8,.. has no visible pattern. But the sequence is generated by the recurrence relation and is given by:

a₁ = a₂ = 1
a₃ = a₁ + a₂
a_n = a_n - 2 + a_n - 1, n > 2

Fibonacci Sequence Formula

If a_n is the n^th term, a_n-1 is the previous term and a_n-2 is the term befor the term a_n-1 then a_n = a_n – 2 + a_n – 1 is the formula for fibonacci sequence.

If we have 2,4,6,8,......, then the n^th term of this sequence can be written as a_n = 2n, where n is a natural number. Similarly, in the sequence of odd natural numbers 1, 3, 5…, the n^th term is given by the formula, a_n = 2n – 1, where n is a natural number.

6. String Sequence

Where a sequence is of of the form a₁, a₂, . . ., a_n or a₁a₂ . . . a_n are often used in computer science.

7. Length Sequence

Where a sequence is of of the string S is the number of terms in the string.

8. Empty String Sequence

Where a sequence is denoted by I, is the string that has no terms and has length 0.

9. Harmonic Sequence

This is a type of sequence where the reciprocal of the terms from an arithmetic sequence. So, if any sequence is in the form of $\frac{1}{x_{1}}, \frac{1}{x_{2}}, \frac{1}{x_{3}}, . . . . . . ., \frac{1}{x_{n}}$ , then the sequence is said to be harmonic sequence.If a, b and c are in the form of arithmetic sequence, then b = $\frac{2 a c}{a + c}$ For example, the sequence $\frac{1}{1}, \frac{1}{2}, \frac{1}{3}, . . . . .$ is a harmonic sequence.

What real-world application that we can used sequence to represent the problem?

A landed house cost $140,000 each.

If we deposit $400 in the bank and earn 10% interest every year, let's find out how many years will it be before we're able to buy this house?

1. Figure out what the problem is asking.
The problem is describing a geometric sequence. If we earn 10% interest per year, each year we'll have 1.1 times as much money as we did the previous year.
After one year we'll have
400(1.1),
after two years we'll have
400(1.1)(1.1),
and after n years we'll have
a_n = 400(1.1)ⁿ.
We want to know what value of n makes a_n ≥ 140,000.

2. Solve the problem.
Solve the inequality.
140,000 < a_n
140,000 < 400(1.1)ⁿ
350 < (1.1)ⁿ
log _1.1350 < n
61.46 < n
It would take 62 years before we had enough money to buy the house.

3. Check the answer.
We'll check the answer by finding a₆₁ and a₆₂.
After 61 years, the amount of money we have is
a₆₁ = 400(1.1)⁶¹ = 133,971.92.
That's not quite enough. After 62 years we have
a₆₂ = 400(1.1)⁶² = 147,369.11.

What is the example of sequence in real - world problem.

Delivery Route Problem:

If we need to leave a place to visit a sequence of locations, each exactly once and then return home, such as might happen with a newspaper delivery route or scheduling bread to be delivered from a bakery to grocery stores.

Reference:

2. Series

What is defined by series?

A series is the sum of the terms of a sequence.
A large uppercase Greek letter Sigma, Σ is used to denote summation.
Let the sequence {a_n } be a_m, a_(m+1), …, a_n. Then, the sum of the terms a_m+a_(m+1)+⋯+a_n can be expressed as:

(read as the sum from j=m to j=n of s_j)

Here, the variable j is called the index of summation, and the choice of the letter j as the variable is arbitrary; that is, we could have used any other letter, such as i or k. Or, in notation,

Here, the index of summation runs through all integers starting with its lower limit m and ending with its upper limit n. A large uppercase Greek letter sigma, Σ, is used to denote summation.

For example:

What is the value of ∑_(j=1 )^5▒j^2 ?

Solution: We have

∑_(j=1)^5▒j^2 = 1^2 + 2^2 + 3^2 + 4^2 + 5^2
=1+4+9+16+25
=55

Type of series

I. Arithmetic Series

A series with a constant difference between the terms is called arithmetic series. For example, 2, 5, 8, 11, 14, ...... is an arithmetic series, where the difference is same between the terms.

If any series is in the form of a + (a + d ) + (a + 2d) + (a + 3d) + ........., it is called the arithmetic series, where a is the first term of the series and d is the difference of it which is known as the common difference of the given series.

Arithmetic Series Formula:
In an arithmetic series, if a is the first term, d is the difference and n is the total number of the terms, then the formula for nth term is given by
a_n = a + (n - 1)d

Sum of Arithmetic Series:

The sum of an arithmetic series S_n is given by the formula

S_n= n/2 [2a+(n-1)d]

II. Geometric Series

A geometric series is one where each successive term is produced by multiplying the previous term by a constant number (called the common ratio in this context). Example:

In general, the geometric series

∑_(n=0)^∞▒z^n

converges if and only if |z| < 1 or -1 < z < 1.

III. Harmonic Series

This is the reciprocal of the arithmetic series. Any series is said to be harmonic series if it is in the form as follows:

1/a+ 1/(a+d)+ 1/(a+2d)+ ……

Example:

1 + 1/2+ 1/3+ ……

For any harmonic series, there is no separate formula for finding the sum of it. But, we can find the sum of any harmonic series by finding the sum of arithmetic series and take the reciprocal of it which is the sum of the harmonic series.

Alternating Harmonic Series:

The formula for alternating harmonic series can be expressed as

∑_(n=1)^∞▒〖(-1)〗^(n - 1)/n=1- 1/2+ 1/3- ……+ (-1)^(n- 1)/n+ ……

The alternating harmonic series is a series which is conditionally convergent.

IV. Alternating Series

An alternating series is a series where terms alternate signs. Examples:

(alternating harmonic series)

and

V. Fibonacci Series

This is the sequence of numbers which is in the form in a way that we found the next number by adding up the two previous numbers before it. Like 2, 2, 4, 6, 10, 16, .........

In the above series,

1. We found number 4 by adding two numbers whose are 2, 2 i.e. 2 + 2.

2. Again, we found the number 6 by adding up 2 and 4 which comes before it.

3. And, the number 6 is found by adding up 4 and 6. And so on.

Fibonacci Series Formula:

If xn is the nth term, xn-1 is the n - 1th term and xn - 2 is the n - 2nd term of any fibonacci series, then we have a formula for it as xn = xn-1 + xn-2

VI. Exponential Series

Exponential series formula is of the form,

e^x=1+ x/1!+ x^2/2!+ x^3/3!+ ……= ∑_(n=0)^∞▒x^n/n!

From the given exponential series formula, we can port value for the exponent 'x' as an infinite series like the given series of ex. If the exponent function of x is n, then the coefficient function of x is 1/n! .

Some of the exponential series formulas are as follows,

1. e^(-x)=1- x/1!+ x^2/2!- x^3/3!+ ……

2. (e^x+ e^(-x))/2=1+ x^2/2!+ x^4/4!+ ……

3. (e^x- e^(-x))/2=x+ x^3/3!+ x^5/5!+ ……

Real-world application that we can used series to represent the problem

Example of real-world problem:

A gardener plans to construct a trapezoidal shaped structure in his garden. The longer side of trapezoid needs to start with a row of 97 bricks. Each row must be decreased by 2 bricks on each end and the construction should stop at 25th row. How many bricks does he need to buy?

Solution :

The longer side of trapezoid shaped garden is containing 97 and each row must be decreased by 2 on each end and the construction must stop when it reaches the 25th row.

If we write the number of bricks in each row as sequence we will get 97, 93, 89,............

Now we need to find number of bricks needed to buy. For that we have to make it as series and we have to find for 25 terms of the series.

Sn = (n/2) [2a + (n-1)d]

a = 97, d = 93-97 = -4, n = 25

S25 = (25/2) [2(97) + (25-1) (-4)]

= (25/2) [194 + (24) (-4)]

= (25/2) [194 - 96]

= (25/2) (98)

= 25 x 49

= 1225 bricks

REFERENCE :

1. http://jwilson.coe.uga.edu/emt668/emat6680.f99/mccallum/emat6690/sequencesandse/Default.htm
2. https://en.wikipedia.org/wiki/Series_(mathematics)#Examples_of_numerical_series
3. https://www.onlinemath4all.com/real-life-problems-involving-arithmetic-series.html
4. https://math.tutorvista.com/discrete-math/series.html
5. https://math.tutorvista.com/discrete-math/exponential-series.html

3. Recurrence Relations

Recursive/ recurrence relations can be defined by descriptions which involve other terms that come before them in sequence.

A sequence is defined recursively provided that:

i) some finite set of values, usually the first one or first few are specified, and

ii) the remaining values of the sequence are defined in terms of previous values of the sequence. A formula which does this is called a recursive formula.

Example:

Let {s_n } be a sequence that satisfies the recurrence relation s_n=s_(n-1)+2 for n=1, 2, 3, … and suppose that s_0=2. What are s_1,s_2 and s_3?

Ans. : s_1=s_0+2=2+2=4

s_2=s_1+2=4+2=6

s_3=s_2+2=6+2=8

Fibonacci Sequence

Useful sequence defined by a recurrence relation.

A sequence of f_0,f_1,f_2,… which is defined by initial conditions: f_0=0,f_1=1, and recurrence relation: f_n=f_(n-1)+f_(n-2) for n=2, 3, 4, …

Example:

Find the Fibonacci numbers f_2 and f_3.

Ans. : f_2=f_1+f_0=1+0=1

f_3=f_2+f_1=1+1=2

How to solve the famous problem, “Towers of Hanoi Problem” that used recurrence relation

The Tower of Hanoi:

A popular puzzle of the late nineteenth century invented by the French mathematician Édouard Lucas, called the Tower of Hanoi, consists of three pegs mounted on a board together with disks of different sizes. Initially these disks are placed on the first peg in order of size, with the largest on the bottom (as shown in Figure 2).

-

FIGURE 2 The Initial Position in the Tower of Hanoi.

The rules of the puzzle allow disks to be moved one at a time from one peg to another as long as a disk is never placed on top of a smaller disk. The goal of the puzzle is to have all the disks on the second peg in order of size, with the largest on the bottom.

Let Hn denote the number of moves needed to solve the Tower of Hanoi problem with n disks. Set up a recurrence relation for the sequence {Hn}.

Solution:
Begin with n disks on peg 1.We can transfer the top n − 1 disks, following the rules of the puzzle, to peg 3 using Hn−1 moves (see Figure 3 for an illustration of the pegs and disks at this point). We keep the largest disk fixed during these moves. Then, we use one move to transfer the largest disk to the second peg. We can transfer the n − 1 disks on peg 3 to peg 2 using Hn−1 additional moves, placing them on top of the largest disk, which always stays fixed on the bottom of peg 2. Moreover, it is easy to see that the puzzle cannot be solved using fewer steps. This shows that
Hn = 2Hn−1 + 1.
The initial condition is H1 = 1, because one disk can be transferred from peg 1 to peg 2, according to the rules of the puzzle, in one move.

FIGURE 3 An Intermediate Position in the Tower of Hanoi.

We can use an iterative approach to solve this recurrence relation. Note that

Hn = 2 Hn−1 + 1

= 2 (2Hn−2 + 1) + 1 = 22 Hn−2 + 2 + 1

= 22 (2Hn−3 + 1) + 2 + 1 = 23 Hn−3 + 22 + 2 + 1

.

.

.

= 2n−1 H1 + 2n−2 + 2n−3 +· · ·+2 + 1

= 2n−1 + 2n−2 +· · ·+2 + 1

= 2n − 1.

We have used the recurrence relation repeatedly to express Hn in terms of previous terms of the sequence. In the next to last equality, the initial condition H1 = 1 has been used. The last equality is based on the formula for the sum of the terms of a geometric series.

The iterative approach has produced the solution to the recurrence relation Hn = 2Hn−1 + 1 with the initial condition H1 = 1. This formula can be proved using mathematical induction.

A myth created to accompany the puzzle tells of a tower in Hanoi where monks are transferring 64 gold disks from one peg to another, according to the rules of the puzzle. The myth says that the world will end when they finish the puzzle. How long after the monks started will the world end if the monks take one second to move a disk?

From the explicit formula, the monks require

264 − 1 = 18,446,744,073,709,551,615

moves to transfer the disks. Making one move per second, it will take them more than 500 billion years to complete the transfer, so the world should survive a while longer than it already has.

REFERENCE :

1. https://shyam.nitk.ac.in/Books/GT%20Books/DiscMaths4CompSc.pdf

2. https://homepages.abdn.ac.uk/k.vdeemter/pages/teaching/CS3518/abdn.only/Rosen-Ed7.pdf