Discrete Mathematics

Verified

Added on  2023/01/05

|10
|1522
|74
AI Summary
This document covers various topics in Discrete Mathematics including theorems, proofs, recursive equations, and number divisibility. It also includes examples and computations for Fibonacci sequences and functions.

Contribute Materials

Your contribution can guide someone’s learning journey. Share your documents today.
Document Page
Discrete Mathematics

Secure Best Marks with AI Grader

Need help grading? Try our AI Grader for instant feedback on your assignments.
Document Page
Table of Contents
1........................................................................................................................................................1
2........................................................................................................................................................2
3........................................................................................................................................................4
4........................................................................................................................................................6
Document Page
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
Document Page
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

Secure Best Marks with AI Grader

Need help grading? Try our AI Grader for instant feedback on your assignments.
Document Page
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
Document Page
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
Document Page
c. Expansion of product of –
(xn + 1) (x + 1)
xn x
= (xn +1 + x1-n + xn-1 + x-(n+1))
5

Paraphrase This Document

Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser
Document Page
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
Document Page
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
Document Page
8
1 out of 10
circle_padding
hide_on_mobile
zoom_out_icon
[object Object]

Your All-in-One AI-Powered Toolkit for Academic Success.

Available 24*7 on WhatsApp / Email

[object Object]