Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Examination, 04-BS-16 Discrete Mathematics, May 2013. Closed book, no aids, 3 hours, 12 questions of 10 marks each (100 marks); the exam instructs "answer 10 of 12" but every question is solved below as a complete study resource.
Reference texts: Rosen, Discrete Mathematics and Its Applications, 7th ed. (logic Ch.1, induction & recursion Ch.5, counting Ch.6, discrete probability Ch.7, relations Ch.9, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.
Approach. Both parts are standard induction proofs — (a) uses simple (weak) induction on $n$ with an algebraic factoring identity; (b) uses strong induction because the recurrence reaches back two terms.
(a) Base case $n=1$. $x^1-1=x-1$, which is trivially divisible by $x-1$.
(a) Inductive step. Assume $x^k-1=(x-1)m$ for some integer $m$ (inductive hypothesis). Then
$$x^{k+1}-1 = x\cdot x^k - 1 = x(x^k-1) + (x-1) = x(x-1)m + (x-1) = (x-1)(xm+1).$$
Since $xm+1$ is an integer, $x^{k+1}-1$ is divisible by $x-1$. By the principle of mathematical induction, $\boxed{x^n-1 \text{ is divisible by } x-1 \text{ for every } n\ge 1}$.
(b) Base cases $n=1,2$. $a_1=1\le 5^0=1$ ✓ and $a_2=2\le 5^1=5$ ✓ (both must be checked explicitly because the recurrence itself only starts at $n=3$).
(b) Strong-induction step. Assume $a_j\le 5^{j-1}$ for every $1\le j<n$ (strong inductive hypothesis), $n\ge 3$. Then
$$a_n = 2a_{n-1}+3a_{n-2} \le 2\cdot 5^{n-2} + 3\cdot 5^{n-3} = 5^{n-3}(2\cdot 5+3) = 13\cdot 5^{n-3}.$$
Since $13\le 25$, $13\cdot 5^{n-3}\le 25\cdot 5^{n-3}=5^{n-1}$. Hence $\boxed{a_n\le 5^{n-1}\text{ for every }n\ge 1}$, completing the strong induction.
Final results — Question 2
Part
Result
(a)
Proved by weak induction: $x^{k+1}-1=(x-1)(xm+1)$
(b)
Proved by strong induction: $a_n\le 13\cdot5^{n-3}\le 5^{n-1}$
