Ancestor Calculation and Growth Patterns

This assignment presents two distinct mathematical problems. The first task requires calculating the total number of ancestors a person would have if tracing their lineage back ten generations. The second problem focuses on analyzing the growth pattern of a child's height between ages 3 and 11, utilizing an arithmetic sequence to predict their height at age 8.

Discrete Mathematics
AMTH140 Assignment 3
STUDENT ID
[Pick the date]

Question 1
(a) Any postage of at least 12 ₡ would be obtained using 3₡ and 7₡ stamps.
Mathematical induction – “In normal mathematical induction, it has been assumed that if the
base case is true then some number n would be true when the case is also true for n+1 (Youse,
2011)
.”
Step 1: Let n = 12, then
12=3 ( 4 ) +7 ( 0 )
Step 2: Let n is an positive integer value for which n ≥ 12
And hence,
n would be written∈the form of a∧b , such as
n=3 a+7 b
Where,
a∧b are also someinteger values for which a ,b ≥ 0.
In this regards, two following conditions would be taken into account.
1. Let a ≥ 2and thus,
3 ( a−2 ) +7 ( b+1 ) =n+1
2. Let a ≤ 1 and thus,
3 a+7 b=n ≥ 12
1

7 b ≥ 9
b ≥ 2
3 ( a+5 )+7 ( b−2 )=n+1
Hence, it can be said that inductive argument to (n+1) is true for all the k values which is smaller
than n i.e. k <n.
 If n = 12, the condition is true because 12₡ would be made from - four 3₡ stamps.
 If n = 13, the condition remains true because 13₡ would be made from – one 7₡ stamps and
two 3₡ stamps.
 If n = 14, the condition remains true because 14₡ would be made from – two 7₡ stamps.
Therefore, based on above discussion, it can be said that strong induction has been formed the
respective proposition for all the respective positive integers. Thus, n+1₡ postages would be
made in either with 7₡ stamps and 3₡stamps as per induction step.
(b) From mathematical induction
3+6+ 9+… … … … .+3 n=3 n ( n+1 )
2
Step 1: Let P ( n )=3+6+9 … … … … .+3 n=3 n ( n+1 )
2
Step 2: For n = 1
LHS = 3
RHS= 3∗1 ( 1+1 )
2 =3
Here, LHS =RHS highlights that P(n) is true for n =1.
Step 3: Let P (k) would be true and hence, P( k+ 1) would also be true (Youse, 2011).
2

Now, assume
P ( k ) =3+6+9+ … … …+3 k =3 k ( k +1 )
2 … . ( 1 )
It is true for k.
Now, for k+1
P ( k +1 ) =3+ 6+9+ …+3 ( k +1 ) = 3 ( k +1 ) ( ( k +1 ) +1 )
2
3+6+ 9+… … .+ ( 3 k +3 )= 3 ( k +1 ) ( k +2 )
2 … .. ( 2 )
From equation (1)
Put k = k+1
P ( k +1 )=3+6+9+… …+3 ( k +1 )= 3 ( k +1 ) ( ( k +1 )+1 )
2
3+6+ 9+… … .+ ( 3 k +3 ) = 3 ( k +1 ) ( k +2 )
2
It can be seen that P(k) would become same as P(k+1) and thus, P (k+1) would be true when
P(k) is true.
The conclusion can be drawn based on the principle of mathematics induction that P(n) would
be true for all the n values , where n is a positive nature number.
Question 2
(a) Value of a1 , a2 ∧a3
3

Value of a1: when n = 1, There are only two disks with same size which would move directly to
the direction of desired pole and hence, a1=2.
Value of a2: when n = 2, There are only four disks with 2 smaller disks and 2 large size disks.
There are six moves are possible by considering that one of a disk is on pole A which is moving
to pole C.
A → B
A → B
A →C
A →C
B→ C
B→ C
There is minimal 6 moves possible. Larger disk would only be moved when the smaller disks
would be removed and reached to the desired pole. There are 2 smaller disks and hence, two
moves are sufficient for this. Moreover, the rest 4 moves would consume by the larger disks.
Further, to move larger disks at least 2 moves is essential and to stack the smaller disks from the
top of lager one needs extra at least 2 move. Thus, a2=6
Value of a3: The two largest disks would not remove till the 4 disks are removed from pole. It
requires minimum 4 moves. These four moves would occupy both poles. Hence, it is essential to
remove the 4 disks from pole and shift one disk to another pole. It needs at least 6 moves. 2
larger disks require 2 moves each. Four smaller disks requires not lower than 6 moves. Therefore
total moves would be =14.
4

(b) Based on the discussion in part (a) , it can be said that recurrences relation for the
sequence would be given below:
an=2 an−1 +2
(c) Put , n =1, 2 and 3 in an=2n+1 −2
It can be seen that the values would be the same which is same as highlighted in part (b) and part
(a).
 Let n=1
Let a0=0
a1=2 a0 +2=2
a1=22−2=2
 Let n=2
a2=2 a2−1+2,=2 a1 +2=2∗2+2=6
a2=22+1−2=23−2=6
 Let n=3
a3=2 a3−1 +2 ,=2 a2 +2=2∗6+2=14
a3=23+1−2=24 −2=14
This is evident from all the above parts. Hence, the given sequence recurrence relation is same as
derived in part (b).
5

Question 3
(a) Recurrence relation
an= an−1
1+an−1
With, a0=1
Method of iteration to establish an explicit formula
At n = 1, a1= a1−1
1+ a1−1
= a0
1+a0
= 1
1+1 = 1
2
At n = 2, a2= a2−1
1+ a2−1
= a1
1+a1
= 1 /2
1+1/2 =1
3 = 1
2+1
At n = 3, a3= a3 −1
1+ a3−1
= a2
1+a2
= 1 /3
1+1/3 = 1
4 = 1
3+1
.
.
.
.
.
.
At n = n, an= an−1
1+ an−1
= 1
n+ 1
6

Therefore, based on the above iteration method, it can be said that for the given recurrence
formula, the explicit formula would be ( 1
n+1 ¿ .
(b) Verification of correctness through mathematical induction:
1+ 1
2 + 1
3 + 1
4 +… … … … .+ 1
n+1 = an−1
1+ an−1
Step 1: Let P ( n )=1+ 1
2 + 1
3 + 1
4 +… … … … .+ 1
n+1 = an−1
1+ an−1
Step 2: For n = 1
LHS= 1
2
RHS= a1−1
1+ a1−1
=1
2
Here, LHS =RHS highlights that P(n) is true for n =1.
Step 3: Let P (k) would be true and hence, P( k+ 1) would also be true.
Now, assume
P ( k )=1+ 1
2 + 1
3 + 1
4 +… … … … .+ 1
k +1 = ak−1
1+ak−1
…. ( 1 )
It is true for k.
Now, for k+1
P ( k +1 )=1+ 1
2 + 1
3 + 1
4 +… … … … .+ 1
(k +1)+1 = ak+1−1
1+ak +1−1
7

1+ 1
2 + 1
3 + 1
4 +… … … … .+ 1
k +2 = ak
1+ak
… .. ( 2 )
From equation (1)
Put k = k+1
P ( k +1 )=1+ 1
2 + 1
3 + 1
4 +… … … … .+ 1
k +1+1 = ak+1−1
1+ ak +1−1
1+ 1
2 + 1
3 + 1
4 +… … … … .+ 1
k +2 = ak
1+ak
It can be seen that P(k) would become same as P(k+1) and thus, P (k+1) would be true when
P(k) is true.
The conclusion can be drawn based on the principle of mathematics induction that P(n) would
be true for all the n values , where n is a positive nature number.
Question 4
(a) Each person has – 2 parents, 4 grandparents, 8 great grandparents and so forth.
Sequence – Geometric sequence
Number of ancestors a person has going back for the given cases =?
 Case 1 – five generation
 Case 2 – ten generation
8

The respective number of ancestors would be 2,4,8,16 … … …
First term = 2
Common ratior = 4
2 = 8
4 =16
8 =2
 Case 1 – five generation
Number of generation n=5
Number of ancestors a person has going back for five generation is given below:
For r >1 i . e .2>1
Sn=a (r ¿¿ n−1)
r−1 ¿
S5=2 (2¿¿ 5−1)
2−1 =62 ¿
Therefore, the number of ancestors for a person has going back for five generation is 62.
 Case 2 – ten generation
Number of generation n=10
Number of ancestors a person has going back for ten generation is given below:
For r >1 i . e .2>1
Sn=a (r ¿¿ n−1)
r−1 ¿
S10=2 (2¿¿ 10−1)
2−1 =2046 ¿
9

Therefore, the number of ancestors for a person has going back for ten generation is 2046.
(b) Normal growth pattern for the children aged 3-11 is following arithmetic sequence.
At age 3 = a = 98.2 cm
At age 5 = 109.8 cm
Arithmetic sequence
a , a+ d , a+2 d , a+3 d , a+4 d , a+5 d … … … … … ……
At the age 4¿ a+ d
At age 5 = a+2d
Hence,
109.8=a+2 d
109.8=98.2+2 d
d=5.8
Hence, the common difference of the arithmetic sequence is 5.8.
The child height at the age 8 would be given below:
At the age 8=a+5 d=98.2+ (5∗5.8 ) =127.2cm
The child height at the age 8 is 127.2 cm.
10

Question 5
(a) Logic has been present in unorganized ever since the humans came into existence. The origin
of logic as studies can be traced to geometry which started during the Egyptians time. Some
progress on logic studies took place during the time of early Babylonians and early Greeks
before Aristotle. Ancient Indian and Chinese civilization also contributed in this regard.
However, it is Aristotle which through syllogisms laid a solid foundation which later
influenced the West. The various Greek scholars of prominence are Thales, Pythagorus,
Plato, Permenides and Aristotle. Aristotle played the most crucial role in the evolving of
logic through various logical works known as Organon (Barwise & Feferman, 2017).
(b) The history of use of mathematical induction can be traced back to the 4th century B.C. when
it was used by Greek mathematician Parmenides. Also, some traces of use of mathematical
induction in a rather implicit manner can also be traced in the work of Fuclid who gave the
world Euclidean Geometry. Further, Bhaskaran cyclic method also made implicit use of the
mathematical induction. In the 10th century A.D., al-Karaji offered an implicit proof of
mathematical induction in case of arithmetic progression. Thus, the early use of mathematical
induction was implicit only. The first explicit use of this technique can be found in the works
of Pascal in the 17th century post which it has been extensively used by various
mathematicians which has led to underlying growth of popularity (Gunderson, 2016).
11

Reference
Barwise, J. & Feferman, S. (2017) Model- Theoretic Logics. Cambridge: Cambridge University
Press.
Gunderson, S.D.(2016) Handbook of Mathematical Induction: Theory and Application, Discrete
Mathematics and its Applications (8th ed.). London: CRC press.
Youse, K. B. (2011) Mathematical Induction (7th ed.). California: The University of California.
References
12

13