Discrete Mathematics Assignment: Induction, Recurrence, and Functions

This document contains a comprehensive solution to a Discrete Mathematics assignment. The solution covers several key areas, including a proof demonstrating that a graph with 'v' vertices and 'e' edges has at least 'v-e' connected components, utilizing induction. It then delves into the Fibonacci sequence, providing proofs for several properties, such as an inequality involving the sequence's terms and divisibility properties. The assignment further explores mathematical induction to prove the divisibility of a specific expression and an inequality involving real numbers. Finally, it includes the computation of values for given recursive functions, including a detailed step-by-step calculation of a function's value based on provided recursive definitions. This assignment provides a valuable resource for students studying discrete mathematics, offering clear explanations and examples of core concepts.

Discrete Mathematics

Table of Contents
1........................................................................................................................................................1
2........................................................................................................................................................2
3........................................................................................................................................................4
4........................................................................................................................................................6

1.
Theorem – A graph with v vertices and e edges has at least v – e connected components.
Proof: By applying induction on edges e –
In case, if e = 0 then each vertex will be connected component which satisfies the clain
But, if e > 0, then pick ab as an edge
Let, G’’ be a graph which is obtained by removing this edge ab
Then, G’’ has at most one more component other than G
By using induction hypothesis,
G’’ must have at least one component as v – (e – 1)
So, it shows G has also at least v – (e – 1) = v – e components.
In this proof, two main approaches are used -
 Spanning tree including the fact that a tree of vertices v has exactly one edge e.
 Induction on the graph size by assuming that G has a connected graph of vertices and
edges, then on removal of edges, graph will split into two parts. By inductive hypothesis
both graphs have at least one edges and removal of any edge both graphs will be not
connected.
1

2.
By Recursive equation –
Fibonacci sequence is recalled as –
f0 = 0
f1 = 1
fn = fn - 1 + fn – 2 for, n ≥ 2
To prove –
a. fn+1 < (13/8)n holds for all n ≥ 1.
Proof: Given,
fn = fn - 1 + fn – 2
By using Recurrence for fn
fk+1 = fk + fk – 1
By using strong induction hypothesis, with n = k and k – 1
= (13/8)k + (13/8)k-1
= (13/8)k (1 + 8/13)
k
= 21 13
13 8
< (13/8)k
This holds the claim that proof the induction step.
b. For fixed natural number k ≥ 1, then number fnk is divisible by fn for all n ≥ 1.
Given that –
f1 = 1 and f2 = 1 which gives odd equal result, then using the claim, fix natural numbers k and n,
f1 = 1 and f2 = 1 will divide fn for all values of n ≥ 1
at k ≥ 2 then by induction hypothesis,
fnk = fk fnk-k-1 + fk-1 fnk-k
By using induction on n,
Assuming that fk divides fnk-k . It proves that fk divides fnk.
2

2n+1 2
c. The equation ∑i=0 fi fi+1 = f2n+2 holds for all natural numbers n ≥ 1.
Given,
f0 = 0
f1 = 1
then,
at n = 1
f1. f2= f 22 = 1
Similarly, using induction hypothesis
fn. fn+1 = f 22n +2
It shows the proof.
3

3.
a. The number 15n+1 + 162n - 1 is divisible by 241 for all n ≥ 1
Proof:
15n+1 + 162n – 1
Here, 16n can be written as (1 + 15)n So,
So, by using induction hypothesis
15n .15+ (1+15)2n . 16-1
240 . 15n + (1 + 15)n . (1 + 15)n
240 . 15n + (1 + 15n) (1 + 15)n
240 .15n + 15n + rest of the terms
241 (15n + ...)
It holds the proof that 15n+1 + 162n - 1 is divisible by 241 for all n ≥ 1.
b. For a fixed real number, x > 0 the inequality
(1 + x)n > 1 + nx + n (n-1) x2 holds for all n ≥ 3
2
Since the base case is n = 3
Therefore,
(1 + x)3 = 1 + x3 + 3x2 + 3x
So, (1+x)3 > 1 + 3x3
So, it holds the axioms.
Using induction hypothesis,
Let n = k, then
(1 + x)k = 1 + kx + k (k-1) k2 ...
2
Then,
As (1+x)k+1 = (1 + x)k . (1+x)
= (1+kx) (1+x)
= (1+ kx2 + x + kx)
> 1 + nx + n (n-1) k2
2
Hence the statement holds for all n ≥ 3 by induction.
4

c. Expansion of product of –
(xn + 1) (x + 1)
xn x
= (xn +1 + x1-n + xn-1 + x-(n+1))
5

4.
Given,
f(0) = −1 base case 0,
f(1) = 0 base case 1,
and f(n) = n · f(n − 1) + f(n − 2)2 recursive case for n ≥ 2.
g(0, m, r, k) = m base case 0,
and
g(n, m, r, k) = g(n − 1, r,(k + 2)r + m2 , k + 1) recursive case for n ≥ 1
h(0, m, r, k) = m base case 0,
h(1, m, r, k) = r base case 1,
and h(n, m, r, k) = (n + k)·h(n − 1, m, r, k) + h(n − 2, m, r, k)2 recursive case for n ≥ 2.
To find –
a) Compute the value of f(5)
Given,
f(n) = n · f(n − 1) + f(n − 2)2
at n = 5
f(5) = 5 · f(5 − 1) + f(5 − 2)2
= 5 · f(4) + f(3)2
So, before proceeding for further calculation, firstly calculate value of f(2), f(3) and f(4) as
f(2) = 2 · f(2 − 1) + f(2 − 2)2
= 2 · f(1) + f(0)2
= 2 x 0 + (-1)2
= 1
6

f(3) = 3 · f(3 − 1) + f(3 − 2)2
= 3 · f(2) + f(1)2
= 3 x 1 + 0
= 3
And,
f(4) = 4 · f(4 − 1) + f(4 − 2)2
= 4 · f(3) + f(2)2
= 4 x 3 + (1)2
= 12 + 1 = 13
So,
f(5) = 5 · f(4) + f(3)2
= 5 x 13 + (3)2
= 45 + 9 = 54 (Ans)
b. Compute the value of g(5, −1, 0, 0)
g(0, m, r, k) = m base case 0,
and
g(n, m, r, k) = g(n − 1, r, (k + 2)r + m2 , k + 1)
then,
take n = 5, m = -1, r = 0 and k =0
g(5, −1, 0, 0) = g(5 − 1, 0, (0 + 2)0 + (-1)2 , 0 + 1)
= g (4, 0, 0, 1)
Further,
As g(0, m, r, k) = m
Then,
g(1,m, r, k) = r
g(2, m, r, k) = k
g (3, m, r, k) = m
and,
g (4, m, r, k) = r
so, g(5, −1, 0, 0) = = g (4, 0, 0, 1) = 0
7

8