This set covers recurrence relations, generating functions, mathematical induction and elementary number theory. You will solve linear homogeneous and non-homogeneous recurrences, read coefficients from generating functions, and use the inductive step correctly. The number theory questions cover gcd and lcm, modular inverses, Euler's totient, Fermat's little theorem and the Chinese remainder theorem. The set suits GATE CS, university semester exams and coding-interview rounds that ask about modular arithmetic.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 18 questions.
Topics covered in this set
- Linear homogeneous recurrences and characteristic roots
- Non-homogeneous recurrences and particular solutions
- Generating functions
- Principle of mathematical induction
- gcd, lcm and modular inverse
- Euler's totient, Fermat's little theorem and CRT
Discrete Mathematics MCQs with answers and explanations
Q1. What is the general solution of a_n = 4a_(n-1) - 4a_(n-2)?
a) a_n = c1 2^n + c2 (-2)^n
b) a_n = c1 4^n + c2
c) a_n = c1 2^n + c2 n^2 2^n
d) a_n = (c1 + c2 n) 2^n
Q2. If a_n = 5a_(n-1) - 6a_(n-2) with a_0 = 1 and a_1 = 4, what is a_4?
a) 130
b) 146
c) 162
d) 97
Q3. With F_0 = 0, F_1 = 1 and F_n = F_(n-1) + F_(n-2), what is F_10?
a) 34
b) 89
c) 55
d) 144
Q4. The Tower of Hanoi recurrence is H_n = 2H_(n-1) + 1 with H_1 = 1. What is the minimum number of moves for 7 discs?
a) 128
b) 63
c) 255
d) 127
Q5. Which sequence has the generating function 1/(1 - 3x)?
a) a_n = 3^n
b) a_n = 3n
c) a_n = n^3
d) a_n = (-3)^n
Q6. What is the coefficient of x^5 in the expansion of 1/(1 - x)^3?
a) 15
b) 10
c) 21
d) 35
Q7. What is the ordinary generating function of the sequence a_n = n (n ≥ 0), that is 0, 1, 2, 3, ...?
a) 1/(1 - x)^2
b) x/(1 - x)
c) (1 + x)/(1 - x)^2
d) x/(1 - x)^2
Q8. What is a particular solution of a_n = 3a_(n-1) + 2^n?
a) a_n = -2^(n+1)
b) a_n = 2^(n+1)
c) a_n = n·2^n
d) a_n = 3^n
Q9. How many bit strings of length 6 contain no two consecutive 0s?
a) 13
b) 21
c) 32
d) 34
Q10. To prove P(n) for all n ≥ 1 by ordinary induction, after the base case P(1), what must the inductive step show?
a) P(k + 1) → P(k) for every k ≥ 1
b) P(1) → P(k) for one particular k
c) P(k) is true for some k ≥ 1
d) P(k) → P(k + 1) for every k ≥ 1
Q11. For every integer n ≥ 1, the number 7^n - 1 is always divisible by which of the following?
a) 6
b) 4
c) 5
d) 8
Q12. What is 7^100 mod 5?
a) 2
b) 1
c) 3
d) 4
Q13. What is lcm(252, 198)?
a) 49896
b) 1386
c) 2772
d) 5544
Q14. What is the multiplicative inverse of 7 modulo 26?
a) 15
b) 11
c) 19
d) 4
Q15. What is Euler's totient φ(36)?
a) 18
b) 12
c) 24
d) 11
Q16. What is the smallest positive integer x with x ≡ 2 (mod 3), x ≡ 3 (mod 5) and x ≡ 2 (mod 7)?
a) 23
b) 53
c) 38
d) 68
Q17. What is the last digit of 3^2026?
a) 3
b) 9
c) 7
d) 1
Q18. How many positive divisors does 360 have?
a) 18
b) 12
c) 24
d) 30
Quick revision notes
- Distinct roots r1, r2: a_n = c1 r1^n + c2 r2^n; repeated root r: a_n = (c1 + c2 n) r^n.
- For f(n) = k·s^n with s not a root, try a particular solution A·s^n.
- 1/(1 - ax) generates a^n; 1/(1 - x)^k has coefficient C(n + k - 1, k - 1) at x^n.
- Tower of Hanoi: H_n = 2H_(n-1) + 1, so H_n = 2^n - 1.
- gcd(a, b) × lcm(a, b) = a × b.
- a has an inverse mod m iff gcd(a, m) = 1.
- Fermat: a^(p-1) ≡ 1 (mod p) for prime p not dividing a; Euler: a^φ(m) ≡ 1 (mod m).
- φ(n) = n Π (1 - 1/p) over the distinct primes p dividing n.
Frequently asked questions
How do I solve a linear homogeneous recurrence with constant coefficients?
Replace a_n by r^n to get the characteristic equation and find its roots. Write the general solution as a combination of r^n terms, multiplying by powers of n for repeated roots, and use the initial conditions to fix the constants.
What is the difference between ordinary and strong induction?
Ordinary induction assumes only P(k) to prove P(k+1). Strong induction assumes P(1), ..., P(k) all hold, which helps when P(k+1) depends on several earlier cases, for example in proving that every integer greater than 1 has a prime factorisation.
How is a modular inverse found in practice?
Run the extended Euclidean algorithm on a and m to get ax + my = gcd(a, m). If the gcd is 1, then x mod m is the inverse of a modulo m.
Comments
Post a Comment