Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Examination, 04-BS-16 Discrete Mathematics, undated sitting (May 2019). Closed book; approved Casio or Sharp calculator only. The exam instructs "answer 10 of the 12 questions"; every question is answered below as a complete study resource.
Source note: This paper is the May 2019 sitting (every page footer reads "04-BS-16/May 2019"). Two printed statements are defective as set and are flagged where they occur: Question 7(a) prints the last term of $\{1,5,9,\dots\}$ as $4n-1$ (the pattern and the stated sum require $4n-3$), and Question 8(b) prints "$n>2$" although $4^n>n^4$ fails at $n=3,4$. Question 12(c)'s parameters also make a connected graph impossible; this is noted at that part.
Reference texts: Rosen, Discrete Mathematics and Its Applications, 7th ed. (Pearson) — used throughout for logic, set theory, functions, combinatorics, probability, induction, asymptotic (Big-O) notation, and graph theory.
Check: The paper prints the last element as $4n-1$. That cannot be right: every listed element $1,5,9,\dots$ is $\equiv1\pmod4$, while $4n-1\equiv3\pmod4$, and the stated sum does not fit a last term of $4n-1$ (the $n$ numbers $3,7,\dots,4n-1$ sum to $2n^2+n$, not $2n^2-n$). With $n$ terms the $n$-th element is $1+4(n-1)=4n-3$, and then the sum is exactly $2n^2-n$. Part (a) is proved for $A=\{1,5,9,\dots,4n-3\}$, the reading the given pattern and answer both require.
Given. (a) an arithmetic sequence $1,5,9,\dots,4n-3$. (b) a recurrence $a_1=2$, $a_i=a_{i-1}+2i-1$.
Find. Closed forms $2n^2-n$ and $n^2+1$ respectively, proved by induction.
Approach. Both are classic weak-induction closed-form proofs: verify the base case, then show the inductive step by adding the next term/applying the recurrence.
a) Prove $\sum_{k=1}^n(4k-3)=2n^2-n$ by induction on $n$.Base case $n=1$: LHS $=4(1)-3=1$; RHS $=2(1)^2-1=1$. Equal. Inductive step: assume $\sum_{k=1}^m(4k-3)=2m^2-m$ for some $m\ge1$. Then $$\sum_{k=1}^{m+1}(4k-3)=\Big(\sum_{k=1}^m(4k-3)\Big)+\big(4(m+1)-3\big)=(2m^2-m)+(4m+1)=2m^2+3m+1.$$ Compare to the claimed formula at $n=m+1$: $2(m+1)^2-(m+1)=2(m^2+2m+1)-m-1=2m^2+4m+2-m-1=2m^2+3m+1$. The two match exactly, so the formula holds for $m+1$. By induction, $\boxed{\sum_{k=1}^n(4k-3)=2n^2-n\text{ for all } n\ge1}$.
b) Prove $a_n=n^2+1$ given $a_1=2$, $a_i=a_{i-1}+2i-1$.Base case $n=1$: $a_1=2$ and $1^2+1=2$. Equal. Inductive step: assume $a_m=m^2+1$ for some $m\ge1$. By the recurrence, $$a_{m+1}=a_m+2(m+1)-1=(m^2+1)+2m+2-1=m^2+2m+2.$$ Compare to the claimed formula at $n=m+1$: $(m+1)^2+1=m^2+2m+1+1=m^2+2m+2$. The two match exactly. By induction, $\boxed{a_n=n^2+1\text{ for all } n\ge1}$.
Question 7 results
Part
Result
a
Proved: $\sum_{k=1}^n(4k-3)=2n^2-n$
b
Proved: $a_n=n^2+1$
Both proofs follow the identical induction template: confirm the base case numerically, then show that adding exactly the "next" term on the left (a new $4(m+1)-3$ summand in (a), or one recurrence application in (b)) reproduces the closed-form formula evaluated at $m+1$. The algebra is symmetric enough that a slip in expanding $(m+1)^2$ is the single most likely error.
