Discrete Mathematics
VerifiedAdded 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.
Discrete Mathematics
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
Table of Contents
1........................................................................................................................................................1
2........................................................................................................................................................2
3........................................................................................................................................................4
4........................................................................................................................................................6
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
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
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.
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
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
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
(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
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
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
= 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
1 out of 10
Related Documents
Your All-in-One AI-Powered Toolkit for Academic Success.
+13062052269
info@desklib.com
Available 24*7 on WhatsApp / Email
Unlock your academic potential
© 2024 | Zucol Services PVT LTD | All rights reserved.