Mathematics Homework: Sequences, Fibonacci Proofs, and Selection Sort

This document presents solutions to a discrete mathematics homework assignment. The assignment includes finding the first five values of sequences defined recursively, proving properties of Fibonacci numbers using their definition, determining which strings belong to a recursively defined set, and simulating the execution of the SelectionSort algorithm on a given list. The solutions demonstrate step-by-step calculations, logical reasoning, and application of mathematical concepts to solve the problems related to sequences, algorithms and proofs. This assignment provides a comprehensive understanding of these fundamental mathematical concepts.

Assignment 3.2 - Section 3.1 Exercises
write the first five values in the sequence:
2. C(1) = 5
C(n) = 2C(n − 1) + 5 for n ≥ 2
Since 2.c(1) = 5, it follows then that C = 2.5,
C(2) = 2*2.5(2-1) + 5
= 10
C(3) = 2*2.5(3-1) + 5
= 15
C(4) = 2*2.5(4-1) + 5
= 20
C(5) = 2*2.5(5-1) + 5
= 25
C(6) = 2*2.5(6-1) + 5
= 30
The first five values are 5,10,15,20,25,30
4. B(1) = 1
B(n) = B(n − 1) + n2 for n ≥ 2
B=1
The second value
B(2)= 1(2-1) + 22
= 5
The third value
B(3)= 1.(3-1) + 32
= 11
The fourth value
B(4)= 1.(4-1) + 42
= 19
The fifth value

B(5)= 1.(5-1) + 52
= 29
6. T(1) = 1
T(n) = nT(n − 1) for n ≥ 2
Since T(1) = 1, it follows then that T=1
Second value
T(2) = 2*1*(2-1)
= 2
The third value
T(3) = 3*1*(3-1)
= 6
The fourth value
T(4) = 4*1*(4-1)
=1 2
The fifth value
T(5) = 5*1*(5-1)
= 20
prove the given property of the Fibonacci numbers directly from the definition:
13. F(n + 1) + F(n − 2) = 2F(n) for n ≥ 3
F(0) =0;
F(1) = 1;
Therefore, for f(n) n≥3
2F(n) = f((n-2) +1)

= f(n-1)
F(n-1) = f(n-1) + f(n)
= 2 f(n)
14. F(n) = 5F(n − 4) + 3F(n − 5) for n ≥ 6
F(6) = f(n-5) + f(n-4) + f(n-3) + f(n-2) + f(n-1) + f(n) ………… equation 1
But
f(n-4) = f(n-3) + f(n-2) + f(n-1) + f(n)………………………………… equation 2
and
f(n-3) = f(n-2) + f(n-1) + f(n) ………………………………. equation 3
and
f(n-2) = f(n-1) + f(n) ……………………………….. equation 4
however, f (0) =0 ………………………………….. equation 5
replacing the equation 2,3,4 in the 1
f(6) = { f(n-5) } + { f(n-3) + f(n-2) + f(n-1) + f(n) } + { f(n-2) + f(n-1) + f(n)} ….
Equation 5
further replacing the equation 2,3,4, 5 in 1
f(6) = { f(n-5) } + { f(n-1) + f(n) + f(n-1) + f(n) + f(n-1) + f(n)+ f(n-1) + f(n) } + { f(n-
1) + f(n)+ f(n-1) + f(n)}
f((n-3)-2) after rearranging the above
f(6) = 3F(n − 5) + 5F(n − 4)
therefore
f(n) = 3F(n − 5) + 5F(n − 4)
15. F(n) = 3F(n − 3) + 2F(n − 4) for n ≥ 5
F(5) = f(n-4) + f(n-3) + f(n-2) + f(n-1) + f(n) …………….. Equation 1
f(n-3) = f(n-2) + f(n-1) + f(n) …………….. Equation 2
f(n-4)= f(n-3) + f(n-2) + f(n-1) + f(n ) …………….. Equation 3

replacing the equation 2, 3 in 1
f(5) = f(n-4) +{ f(n-2) + f(n-1) + f(n) }
= f(n-4) +{f(n-1) + f(n) + f(n-1) + f(n) }
Rearranging the above
F(5) = 3F(n − 3) + 2F(n − 4)
Therefore
F(n) = 3F(n − 3) + 2F(n − 4)
49. A set S of strings of characters is defined recursively by
1. a and b belong to S.
2. If x belongs to S, so does xb.
Which of the following strings belong to S?
a. a b. ab c. aba d. aaab e. bbbbb
since xb belongs to S therefore ab belongs to S.
84. Simulate the execution of algorithm SelectionSort on the following list L; write the
list after every
exchange
that changes the list.
9, 0, 2, 6, 4
Arr[ ] = 9,0,2 6 4
Finding the first minimum element in array [0…..4] and place it at the beginning of the
array
0, 9 ,2 6 4
Finding the second minimum element in array [1…..4] and place it at the beginning of
the array
0, 2, 9,6, 4

Finding the third minimum element in array [2…..4] and place it at the beginning of the
array
0,2, 4, 9, 6
Finding the fourth minimum element in array [3…..4] and place it at the beginning of
the array
0,2,4,6,9