Disc. Math. 11 November 2024.

Disc. Math. 6 November 2024.

Disc. Math. 4 November 2024.

Disc. Math. final exam (sample)

1.

• How many seven digit numbers can be formed from the digits 1,1,2,2,3,3,3?
• How many nine digit numbers can be formed from the digits 1,1,2,2,3,3,3,3,3?
• How many six digit numbers can be formed from the digits 0,1,2,3,3,3?
• How many eight digit numbers can be formed from the digits 0,1,1,2,2,3,3,3?

2. How many integer solutions do the following equations have?

• \(w + x + y + z = 12,\) where \(w \geq 2 , x\geq 2 , y\geq 2 , z \geq 2;\)
• \(w + x + y + z = 10,\) where \(w \geq 0, x\geq 1, y\geq 2, z \geq 3;\)
• \(v + w + x + y + z = 15,\) where \(v \geq 1, w \geq 0, x\geq 1, y\geq 3, z \geq 3.\)

3. Use the Euclidean algorithm to find \(\gcd(a,b)\) and compute integers \(x\) and \(y\) for which \[ ax+by=\gcd(a,b): \] (I) \(a=1717, b=1479\), (II) \(a=2323, b=2001.\)

4. Determine all non-negative integral solutions of the equation \[ 13x+19y=234. \]

5. Provide a bound \(N\) for \(n\) such that the equation is solvable in non-negative integers if \(n\geq N:\) \[ 7x+17y=n. \]

6. Expand the following expression using the binomial theorem: \[ \left(\frac{x}{3}-2\right)^3. \]

7. By using mathematical induction, show that \(4^n + 15n - 1\) is divisible by 9 for all \(n \geq 1.\)

8. Prove that \(n^3+2n\) is divisible by 3 for all positive integers \(n.\)

9. Prove by induction that \[2^n \lt n!\] for any positive integer \(n\geq 4\).

10. Prove that \[ \sum_{k=1}^n\frac{1}{(3k-1)(3k+2)}=\frac{n}{6n+4} \] for every positive integer \(n\).

11. Prove that \[ \sum_{k=1}^n\frac{1}{k(k+1)(k+2)}=\frac{n(n+3)}{4(n+1)(n+2)} \] for all positive integer \(n\).

12. Let \(a_1=1, a_2=6\) and \(a_{n+1}=7a_n-12a_{n-1},n\geq 2.\) Prove that \[ a_n=3\cdot 4^{n-1}-2\cdot 3^{n-1} \] for all positive integer \(n\).

13. Consider the sequence of real numbers defined by the relations \[x_1=1\] and \[x_{n+1}=\sqrt{1 + 2x_n}\] for \(n\geq 1.\) Prove that \(x_n\lt 4\) for all \(n\geq 1.\)

14. Prove that \[ 10^{n}-3^n \] is a multiple of 7 for every positive integer \(n\).

15. Prove that \[ \prod_{k=n+1}^{2n}k=2^n\prod_{k=1}^n (2k-1) \] for all positive integer \(n.\)

In what follows \(F_n\) denotes the Fibonacci sequence, which is defined by \[ F_0=0,\quad F_1=1,\quad F_n=F_{n-1}+F_{n-2},\quad n\geq 2. \]

16. Prove by induction that \[\sum_{i=0}^{n}F_i=F_{n+2}-1.\]

17. Prove by induction that \[\sum_{i=0}^{n-1}F_{2i+1}=F_{2n}.\]

18. Prove by induction that \[\sum_{i=1}^{n}F_{2i}=F_{2n+1}-1.\]

19. Prove by induction that \[\sum_{i=1}^{n}F_i^2=F_{n}F_{n+1}.\]

20. Prove that \[F_n^2-F_{n+1}F_{n-1}=(-1)^{n-1}.\]

21. Prove by induction the following divisibility properties of the Fibonacci numbers.

1. 2 divides \(F_{3n},\)
2. 3 divides \(F_{4n},\)
3. 5 divides \(F_{5n}.\)