Discrete Mathematics: Recurrence Relations and Password Analysis

This discrete mathematics assignment delves into recurrence relations, bit strings, and password combinations. It begins by defining a recurrence relation for bit strings, deriving its characteristic equation, and finding a closed-form solution. The assignment then identifies a reasoning error in assuming the uniqueness of generated members in a set. Furthermore, it analyzes password generation strategies, including determining the number of possible passwords of varying lengths based on a given dictionary and establishes a recurrence relation for password generation, and calculates characteristic roots. The solution uses Wolfram to find the characteristic roots for the equation. This document is contributed by a student and is available on Desklib, a platform that provides a variety of study tools for students.

Running head: MATHEMATICS 1
Discrete Mathematics
Name
Institution

MATHEMATICS 2
Question 1
Part a
a1=a2=1 since there is an exactly 1-bit string of length 1 and a 1-bit string of length 2 in S.
Part b
The recurrence relation is: an=an−1 +2 an−2 as long as n>2. For such n, no bit strings in S
whose membership is directly given implying that such bit string c must have been generated by
three cases of recursion rules as shown in the proceeding section.
c=10 b for some b ∈ S of lengthn−2 …case 1
c=11 b for some b ∈ S of length n−2 …case 2
c=0 b for some b ∈ S of length n−1 … case 3
In case 1 and 2, there are exactly an−2 choices each for b, and in case 3, there are an−1choices for
b which results in an−1+2 an−2 choices for c.
Part c
We know that the characteristic values from the equation is r2−r−2= ( r +1 ) ( r −2 )=0 are -1 and
2 denoting that the general equation is an= A(−1)n +B(2¿¿ n)¿
Part d
Substituting the initial conditions yields the equations:
− A+2 B=1
A+4 B=1

MATHEMATICS 3
Solving the two simultaneous equations for A and B yields: A=−1
3 and B= 1
3
The closed-form solution becomes: an=−1
3 ( −1 ) n + 1
3 (2¿ ¿ n) ¿
Part e
Obtain S(N ) by adding an for n=1¿ N by using the linearity of the summation operation.
S ( N )=∑
n=1
N
an=−1
3 ∑
n=1
N
(−1 )n+ 1
3 ∑
n=1
N
2n
Factoring the common quotient from each of the summation formula we get:
S ( N ) = 1
3 ∑
n=0
N−1
( −1 ) n + 2
3 ∑
n=0
N−1
2n
S ( N ) = 1
3
( −1 ) N −1
−1−1 + 2
3
2N −1
2−1
Simplifying the equation yields:
S ( N ) =− ( −1 ) N +1+4 ( 2N −1 )
6
S ( N )= 1
6 ( (−1 )N +1 +2N+ 2−3 )
Question 2
The reasoning error is tactically assuming that the recursion rules produce members of S
uniquely. That is applying two different rules to dissimilar b ∈ S results in different c. In this
case, 01 , b1 ,∧0 b2 may well be the same bit string. Indeed, they are, if 1 b1=b2. Which is the case

MATHEMATICS 4
when b1=1∧b2=11. For instance, an=an−1 +2 an−2 is not true for all n>2 because we may be
double-counting some bit strings of length n.
Question 3
Part a
Since each of the generated passwords has at least one of the dictionary words with the shortest
word being pear, these an are all equal to zero.
Part b
We know that each dictionary word contains at least four letters implying that a combination of
any 2 words has a minimum of 8 letters. As a result, any password of a length less than 8 can
only contain one dictionary word. Hence, a4=1∧a5=1because of a 4-letter word and a 5-letter
word (apple) respectively. On the other hand, a6=2 since there are two 6-letter words in the
dictionary (orange and banana). a7=0 because no 7-letter word exists in the dictionary.
Part c
Since all dictionary words have at least 4 letters, any combination of 3 words could have at least
12 letters. Besides, all words in the dictionary have a maximum of 6 letters implying that 7-11
letters length passwords can be only 2-word combinations.
The length of a 2-word combination is the sum of individual word lengths. The available
individual word lengths are 4, 5, and 6 with each having a password length of n ∈{8,9,10,11}.
Each corresponds to an ordered pair derived from D={4,5,6 } with sum n.
Writing 8 as a sum of D elements results to 8=4 +4. The word “pear” is the only one with a
length of 4. Therefore, there is only one 8-letter password “pearapple” implying that a8=1.

MATHEMATICS 5
Similarly, 9=5+4=4+5 are the only ways of writing 9 as a sum of elements of D. There are
single words with length 4 and 5 respectively denoting that the two 9-letter passwords are
“applepear” and” pearapple.” Hence, a9=2. In the same way, a10=5 and a11=4
Part d
A password P of length n (n is 10 or more) cannot be a single dictionary word, so it must have
been created as the concatenation of another password and one of the dictionary words. Since
there are 4 dictionary words, P must be one of the following:
P= pear P4 where P4 is a password of length n – 4
P=apple P5 where P54 is a password of length n−5
P=orange P6 where P6 is a password of lengthn−6
P=bananaQ6 where Q6 isa password of length n−6
Therefore, P4 , P5 , P6 ,∧Q6 have an−4 , an−5 , an−6 ,¿ an−6 choices respectively. P has a total of
an−4 +an−5 +2 an−6 choices.
As it can be seen, the passwords are different since each one of them starts with a unique letter
implying that there is no double-counting danger.
Part e
The characteristic equation is: is r6 −r2−r −2=0
Part f
Using Wolfram, the characteristic roots are:

MATHEMATICS 6
r1=−1.13650
r2=1.3086 0
r3 =−0.5+ j 0.8603 0
r 4=−0.5− j 0.8603 0
r5 =0.41398+ j 1.0832 4
r6 =0.41398− j1.0832 4
Part g
an= A(−1365)n + B(1.3086¿¿ n)+ ( C + jD ) (−0.5+ j 0.8603 )n + ( C− jD ) (−0.5− j 0.8603 )n+ ( E+ jF ) ( 0.41398+ j1.083