Discrete Mathematics Assignment: Induction, Number Theory Problems

This document presents solutions to a variety of mathematical problems. The first section focuses on mathematical induction, providing proofs for several summation formulas and inequalities. The solutions demonstrate the base case and the inductive step, proving the validity of each formula for all natural numbers. The second section delves into number theory, including problems related to prime numbers, such as proving that certain expressions cannot be prime and exploring twin primes. The document also covers problems related to the greatest common divisor (GCD) and least common multiple (LCM), including calculations using the Euclidean algorithm and determining the relationship between GCD, LCM, and the product of two numbers. Finally, the assignment explores the concept of divisibility and prime factorization.

1)
∑
k =1
n
k ( k +1 )= 1
3 n ( n+1 ) ( n+2 )
LHS=RHS for k=n=1
That is P(1) is true.
Assume P(k) is true and P(n) is true.
P(k)=
∑
k =1
n
k ( k +1 )
P(n)= 1
3n(n+1)(n+2)
= 1
3 ( n3 +3 n2 +2 n)
We need to prove P(k+1) & P(n+1) is true.
LHS=,
P(k+1)=
∑
k =1
n
( k +1 ) ( k +2 )
∑
k =1
n
(k2 +3 k + 2)
¿ ∑
k=1
n
k 2+∑
k=1
n
3 k +∑
k=1
n
2
= n ( n+1 ) ( 2 n+1 )
6 + 3 n ( n+1 )
2 +2 n
¿ n ( 2 n2+3 n+ 1 ) +9 n2 +9 n+12 n
6
¿ 2n3+12 n2 +22 n
6
¿ 1
3 ( n3 +6 n2+11n )
RHS,

P(n+1)=
¿ 1
3 ( ( n+ 1 )3+3 ( n+ 1 )2+2 ( n+1 ) )
¿ 1
3 ( n3 +6 n2+ 11n+6 )
¿ 1
3 ( n3 +6 n2+ 11n ) + 1
3∗6
Where the last term is a multiple of n3 +6 n2+11 n.
Therefore LHS=RHS
Therefore P(k+1) and P(n+1) is also true whenever P(k) and P(n) is true.
Hence, by mathematical induction, P(n) and P(k) is true for all n, k ϵ N.
2) To prove 2n+1 is less than n2 +3
Let P(n): 2n+1<n2 +3
P(1): 3<4, which is true.
Assume P(k) is true.
P(k):
2k+1<k 2+3
We have to prove P(k+1) is also true.
P(k+1):
LHS: 2k+3
RHS: (k + 1)2 +3
=k 2+2 k +1+3
=k 2+2 k + 4
=k(k+2)+4
Which is greater than LHS.
Therefore P(k+1) is also true whenever P(k) is true.
Hence, by mathematical induction P(n) is true for all n ϵ N.

3)
∑
k =1
n
3k= 1
2 ( 3n +1−3 )
Let P(n): ∑
k =1
n
3k= 1
2 ( 3n +1−3 )
P(1)=
LHS, =3
RHS, =3
Therefore P(1) is true.
Assume P(k) is true,
P(k):
LHS =
∑
k =1
n
3k
¿ 3+32 +33 … … …+3k
This is equal to RHS,
That is, 3+32 +33 … … …+3k= 1
2 ( 3k+1−3 )
We need to prove P(k+1) is also true,
P(k+1)=
∑
k +1=1
k
3k+1
¿ 3+32 +33 + …3k+3k+1
¿ 1
2 ( 3k +1−3 ) +3k+1
¿ ( 1
2 +1 ) 3k +1− 3
2
¿ 3
2 ( 3k+1 )− 3
2

¿ 3k+2 −3
2
Which is equal to RHS,=
1
2 (3k+2−3)
Therefore LHS = RHS,
Therefore P(k+1) is true whenever P(k) is true,
Hence by mathematical induction, P(n) is true for all n ϵ N.
4) To prove 25n +5n is a multiple of 10
Let P(n)= 25n +5n
P(1)= 25+5
=30 which is a multiple of 10
Therefore P(1) is true.
Assume P(k) is true,
P(k)= 25k +5k
We need to prove P(k+1) is true,
P(k+1)= 25k +1+ 5k+1
= 25k .25+5k .5
=25(25k +5k−5k ¿+5k .5
=25(10p- 5k ¿+5k .5, where 25k +5k is a multiple of 10=10 p
=25*10p-25 ¿ 5k +5*5k
=25*10p-20* 5k
Which is a multiple of 10.
Therefore P(k+1) is true whenever P(k) is true.
Hence by mathematical induction P(n) is true for all n ϵ N.
5)

an+1=2 an , a0=1
Putting n=0,
a1=2∗a0
¿ 2
Putting n=1,
a2=2 a1
¿ 4
Similarly, a3=8 , a4 =16 …∧so on
In general, an=2n ,n ϵ N.
Let P(n): an=2n
P(1)=a1=¿ 21
Which is true.
Assume P(k) is true,
P(k)= ak=2k ,
To prove P(k+1),
P(k+1)= ak+1=2k+1
= 2* 2k
That is ak+1=2∗ak
Therefore P(k+1) is true whenever P(k) is true.
Hence by mathematical induction, P(n) is true for all nϵN.
6) 877 is a prime number.
877 is not divisible by the following prime numbers :-
2,3,5,7,11,13,17,19,23,29
By 2,
877
2 =438.5
which is not a whole number,

By 3,
877
3 =292.333
which is not a whole number,
By 5,
877
5 =175.4
which is not a whole number,
By 7,
877
7 =125.285
which is not a whole number,
By 11,
877
11 =79.72
which is not a whole number,
By 13,
877
13 =67.46
which is not a whole number,
By 17,
877
17 =51.588
which is not a whole number,
By 19,
877
19 =46.15
which is not a whole number,
By 23,
877
23 =38.13

which is not a whole number,
By 29,
877
29 =30.24
which is not a whole number.
7)
p is a prime greater than 2, p+1 cannot be prime,
Let p =3,
p+1=4, which is divisible by 2,
Let p=5,
p+1 =6, which is divisible by 2 & 3
Let p=7,
p+1=8,
Let p=11,
p+1=12
and so on…
p+1 is always even,
Therefore, p+1 cannot be prime.
8)
p & p+2 are both prime – pair of twin primes.
p>10,
let p=11,
p+2=13
Therefore they are twin primes,
Let p=17
p+2=19
Therefore they are twin primes,

Let p=41,
p+2=43, they are twin primes,
Therefore there exists twin primes p,p+2 with p>10.
9)
2221=a
2237=b
2239=c
2243=d,
If a
b = c
d ,
then ,a∗d =b∗c
But here a
b ≠ c
d ,
Therefore, a∗d ≠ b∗c
10)
51984−1 cannot be prime
5n −1 is always even,
Therefore, 51984−1 cannot be prime
11)
a)list of all positive divisors of p2 q3= p,q,1
b)GCD of p4 q4∧ p6 q3= p4 q3
c)LCM of p4 q4∧ p6 q3= p6 q4
12)
GCD of 35&10 using Euclidean Algorithm,
GCD of (10,35)=
35= 10q+r
35=10*3 + 5
10=5*2+0

Therefore GCD = 5
LCM*GCD= product of two numbers
LCM*5=350
LCM=70
13)
GCD of two numbers = 3, LCM=30
GCD*LCM= product of two numbers;
3*30=a*b
Therefore the two numbers are 3 and 30.
(here the product is 90 therefore the only numbers are 3 & 30)
14)
GCD=5
LCM=11
GCD*LCM=55
Therefore it is not possible to have two positive integers with GCD=5 &
LCM=11 as 55 is only divisible by 5 and 11.