Math 2020: Discrete Mathematics - Induction Exercises and Proofs

This assignment provides solutions to induction exercises in Discrete Mathematics, focusing on proving various summation formulas and relationships using mathematical induction. Problems include proving formulas related to Fibonacci numbers and other mathematical expressions. The solutions demonstrate the application of the principle of mathematical induction, including establishing a base case, assuming the statement holds for n=k, and then proving that it holds for n=k+1. The assignment covers problems related to summations and algebraic expressions and is intended for students studying discrete mathematics. Desklib offers a wide range of study resources, including past papers and solved assignments, to support students in their academic endeavors.

[Type the company name]
Discrete Mathematics
Student Name
[Pick the date]

Question 1
For n ≥ 1: F1 +F3 + F5+… … … … F2 n−1=∑
k =1
n
F2 k−1=F2n
Prove by Induction
Let the induction basis is as shown below:
n=1
F1=1
F2=1
Now,
F2∗1−1 =F2∗1
It means the statement holds for n=1
Now,
Inductive step
Let said that the statement holds for n = m and thus,
F1+F3 +… … ……+F2 m−1=F2 m
For n=m+ 1,
F1+F3 +… … …… + F2(m+1)−1=
F1+F3 +… … ……+F2 m+2−1=¿
F1+F3 +… … ……+F2 m+1=¿
Now,
1

F1+F3 +… … ……+F2 m−1+F2 m+1
F2m + F2 m+1
F2m+2
F2 ( m+1 )
F2n as n = m+1
Proved
So it is apparent from the above that the statement also holds for n = m+1. It can be seen that if
the statement is true for n and also for n+1then based on the mathematic induction the
summation can be proved.
Therefore, the conclusion can be made that based on the mathematical induction that the
statement is true for all the values of n.
Question 3
Step 1
Let n = 2
L . H . S .=( 1
1∗2 )= 1
2
R . H . S .=1− ( 1
2 )= 1
2
Hence, the given expression is true for n=2
Step 2
Let n=k where k ≥ 2
2

L . H . S .= 1
1∗2 + 1
2∗3 +… … .+ 1
[ ( k −1 ) k ]
R . H . S .=1− ( 1
k )
Assume that L.H.S. = R.H.S for n=k
Step 3
Now we need to prove that the relationship holds for n=k+1 assuming that it is true for n=k
L . H . S .= 1
1∗2 + 1
2∗3 + … … .+ 1
[ ( k −1 ) k ] + 1
[ k ( k + 1 ) ]
But, 1
1∗2 + 1
2∗3 +… … .+ 1
[ ( k−1 ) k ] =1− ( 1
k ) as highlighted in step 2
Hence, L . H . S .=1− ( 1
k ) + 1
[ k ( k +1 ) ]
Using partial fractions, 1
[ k ( k +1 ) ] =( 1
k )– ( 1
k +1 )
Hence,
L . H . S .=1− ( 1
k )+ ( 1
k ) – ( 1
k +1 )=1−( 1
k +1 )
R . H . S .=1− ( 1
k +1 )
Since L.H.S. = R.H.S. hence, proved
Question 4
For n ≥ 0 ; ∑
k=0
n
( ak−ak+1 )=a0 −an +1
3

Step 1
Put n=0 ,then k=0
a0−a1 =a0 −a1
Step 2
Let n=m
And let assume that m ≥0
L.H.S . = R.H.S.
Step 3
Now n=m+1
Hence, LHS = (a0 – a1) + (a1 – a2) + (a2-a3) +………+ (am – am+1) + (am+1 – am+2)
However, from step 2, (a0 – a1) + (a1 – a2) + (a2-a3) +………+ (am – am+1) = a0 – am+1
Thus, LHS = a0 – am+1 + am+1 – am+2 = a0 - am+2
Also, RHS = a0 - am+2
4