Final Examination 2024 (13th Batch) — Full Solution

Eight questions, answer any five, 14 marks each — recurrence relations, combinatorics, modular arithmetic, probability & Bayes' theorem, Markov chains, differential calculus, gradient descent, Lagrange multipliers, sampling methods, confidence intervals, and hypothesis testing.

Question 1 — Recurrences, Pascal's Identity, and Eulerian Numbers

(a) Expand, sum, and close $T(n) = n + T(n-1),\ T(1) = 1$

Concept Needed

A linear recurrence like this is solved by unrolling it repeatedly until it hits the base case, then rewriting the accumulated terms as a summation.

Step 1: Expand the Recurrence

$T(n) = n + T(n-1) = n + (n-1) + T(n-2) = n + (n-1) + (n-2) + T(n-3) = \cdots$

Continuing until the base case $T(1) = 1$:

$T(n) = n + (n-1) + (n-2) + \cdots + 2 + T(1)$

Step 2: Express as a Summation

$T(n) = \sum_{k=2}^{n} k + T(1) = \sum_{k=2}^{n} k + 1 = \sum_{k=1}^{n} k$

Step 3: Closed Form and Complexity

$T(n) = \sum_{k=1}^{n} k = \frac{n(n+1)}{2}$

(b) Solve $a_n = 3a_{n-1} + 2,\ a_0 = 1$

Step 1: Homogeneous Solution

The homogeneous part $a_n = 3a_{n-1}$ gives $a_n^{(h)} = C \cdot 3^n$.

Step 2: Particular Solution

Try a constant $a_n^{(p)} = A$: $A = 3A + 2 \Rightarrow -2A = 2 \Rightarrow A = -1$.

Step 3: General Solution and Initial Condition

$a_n = C \cdot 3^n - 1$

Using $a_0 = 1$: $C \cdot 1 - 1 = 1 \Rightarrow C = 2$.

(c) Prove $\dbinom{n+1}{k} = \dbinom{n}{k-1} + \dbinom{n}{k}$

Combinatorial proof. $\dbinom{n+1}{k}$ counts the number of $k$-element subsets of a set of $n+1$ elements, say $\{1, 2, \dots, n, n+1\}$. Split these subsets by whether they contain the element $n+1$:

• Subsets containing $n+1$: choose the remaining $k-1$ elements from the other $n$ elements $\Rightarrow \dbinom{n}{k-1}$ ways.
• Subsets not containing $n+1$: choose all $k$ elements from the other $n$ elements $\Rightarrow \dbinom{n}{k}$ ways.

Every $k$-subset falls into exactly one of these two disjoint cases, so

$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k} \qquad \blacksquare$

(d) Eulerian Triangle up to Row $n = 4$

$A(n,k) = (n-k)A(n-1,k-1) + (k+1)A(n-1,k), \qquad A(1,0)=1,\ A(n,k)=0 \text{ for } k<0 \text{ or } k \ge n$

Step 1: Row $n=2$

$A(2,0) = (2)A(1,-1) + (1)A(1,0) = 0 + 1 = 1$

$A(2,1) = (1)A(1,0) + (2)A(1,1) = 1 + 0 = 1$

Step 2: Row $n=3$

$A(3,0) = 3A(2,-1)+1\cdot A(2,0) = 0+1 = 1$

$A(3,1) = 2A(2,0)+2A(2,1) = 2(1)+2(1) = 4$

$A(3,2) = 1\cdot A(2,1)+3A(2,2) = 1+0 = 1$

Step 3: Row $n=4$

$A(4,0)=4A(3,-1)+1\cdot A(3,0)=0+1=1$

$A(4,1)=3A(3,0)+2A(3,1)=3(1)+2(4)=11$

$A(4,2)=2A(3,1)+3A(3,2)=2(4)+3(1)=11$

$A(4,3)=1\cdot A(3,2)+4A(3,3)=1+0=1$

Question 2 — Summation Techniques

(a) Evaluate $\displaystyle\sum_{k=1}^{n} (-1)^k \frac{k}{4k^2-1}$

Step 1: Partial Fractions

Since $4k^2-1=(2k-1)(2k+1)$, write $\dfrac{k}{(2k-1)(2k+1)} = \dfrac{1}{4}\left(\dfrac{1}{2k-1}+\dfrac{1}{2k+1}\right)$.

Let $b_k = \dfrac{1}{2k-1}$, so $b_{k+1} = \dfrac{1}{2k+1}$. The sum becomes

$\sum_{k=1}^{n}(-1)^k \cdot \frac{1}{4}(b_k + b_{k+1})$

Step 2: Telescope

Each term contributes $(-1)^k b_{k+1}$, which is exactly canceled by the next term's $(-1)^{k+1}b_{k+1}$ contribution. Only the very first and very last pieces survive:

$\sum_{k=1}^{n}(-1)^k(b_k+b_{k+1}) = -b_1 + (-1)^n b_{n+1}$

Step 3: Substitute Back

$b_1 = 1$ and $b_{n+1} = \dfrac{1}{2n+1}$, so

$\sum_{k=1}^{n}(-1)^k\frac{k}{4k^2-1} = \frac{1}{4}\left[-1 + \frac{(-1)^n}{2n+1}\right] = -\frac{1}{4} + \frac{(-1)^n}{4(2n+1)}$

Verification

For $n=1$: formula gives $-\frac14 - \frac{1}{12} = -\frac13$. Direct computation: $(-1)^1\frac{1}{3} = -\frac13$. Matches.

(b) Solve $T_0=0,\ T_n = 2T_{n-1}+1$ using a summation factor

Step 1: Divide by $2^n$

$T_n - 2T_{n-1} = 1 \ \Longrightarrow\ \frac{T_n}{2^n} - \frac{T_{n-1}}{2^{n-1}} = \frac{1}{2^n}$

Let $S_n = T_n/2^n$, so $S_n - S_{n-1} = 1/2^n$ with $S_0 = 0$.

Step 2: Sum the Telescoping Series

$S_n = S_0 + \sum_{k=1}^{n}\frac{1}{2^k} = 1 - \frac{1}{2^n}$

Step 3: Recover $T_n$

$T_n = 2^n S_n = 2^n\left(1-\frac{1}{2^n}\right)$

(c) Prove $3\square_n = n\left(n+\frac12\right)(n+1)$ given $\square_n = \dfrac{n(n+1)(2n+1)}{6}$

$3\square_n = 3 \cdot \frac{n(n+1)(2n+1)}{6} = \frac{n(n+1)(2n+1)}{2} = n(n+1)\cdot\frac{2n+1}{2}$

Since $\dfrac{2n+1}{2} = n + \dfrac12$,

$3\square_n = n(n+1)\left(n+\frac12\right) = n\left(n+\frac12\right)(n+1) \qquad \blacksquare$

(d) Perturbation Method

Definition. The perturbation method finds a closed form for a sum $S_n = \sum_{k=0}^n a_k$ by writing $S_{n+1}$ two different ways — once by adding the last term to $S_n$, and once by pulling the first term out of $S_{n+1}$ — then equating and solving for $S_n$.

Example. For $S_n = \sum_{k=0}^n x^k$:

$S_{n+1} = S_n + x^{n+1} \qquad \text{(add last term)}$

$S_{n+1} = x^0 + \sum_{k=1}^{n+1}x^k = 1 + x\sum_{k=0}^{n}x^k = 1 + xS_n \qquad \text{(pull out first term)}$

Equating: $S_n + x^{n+1} = 1 + xS_n \Rightarrow S_n(1-x) = 1-x^{n+1} \Rightarrow S_n = \dfrac{1-x^{n+1}}{1-x}$, the familiar geometric series formula.

Question 3 — Number Theory

(a) Coprime Integers and Relatively Prime Numbers

Coprime integers (equivalently, relatively prime numbers): two integers $a,b$ with $\gcd(a,b) = 1$ — they share no common factor other than $1$.

(b) $\gcd(401,700)$ via Extended Euclidean Algorithm

Step 1: Euclidean Algorithm (Forward Pass)

So $\gcd(401,700) = 1$.

Step 2: Back-Substitution

Working back up from $1 = 4 - 1\cdot 3$, repeatedly substituting each remainder:

$1 = 4 - 1(3) = 2(4) - 7 = 2(95) - 27(7) = 29(95) - 27(102) = 29(299) - 85(401) = 114(700) - 199(401)$

(c) Remainder of $45^{91}$ mod $89$

Since $89$ is prime, Fermat's Little Theorem gives $45^{88} \equiv 1 \pmod{89}$.

$45^{91} = 45^{88}\cdot 45^3 \equiv 45^3 \pmod{89}$

Step 1: Compute $45^2 \bmod 89$

$45^2 = 2025 = 22(89) + 67 \ \Rightarrow\ 45^2 \equiv 67 \pmod{89}$

Step 2: Compute $45^3 \bmod 89$

$45^3 \equiv 45 \times 67 = 3015 = 33(89) + 78 \ \Rightarrow\ 45^3 \equiv 78 \pmod{89}$

(d) Solve $91x \equiv 65 \pmod{260}$

Step 1: Check Solvability

$\gcd(91,260):\quad 260 = 2(91)+78,\ 91=1(78)+13,\ 78=6(13)+0 \ \Rightarrow\ \gcd=13$

Since $13 \mid 65$, solutions exist — exactly $13$ of them, modulo $260$.

Step 2: Reduce the Congruence

Divide through by $13$: $\dfrac{91}{13}=7,\ \dfrac{260}{13}=20,\ \dfrac{65}{13}=5$, giving

$7x \equiv 5 \pmod{20}$

Step 3: Solve the Reduced Congruence

$\gcd(7,20)=1$. Inverse of $7$ mod $20$: $7\times 3 = 21 \equiv 1 \Rightarrow 7^{-1}\equiv 3$.

$x \equiv 3\times 5 = 15 \pmod{20}$

Step 4: Lift Back to Modulus 260

Question 4 — Probability, Bayes' Theorem, and Markov Chains

(a) Wet Grass — Total Probability and Bayes' Theorem

Given: $P(R=1)=0.3,\ P(W=1\mid R=1)=0.9,\ P(W=1\mid R=0)=0.2$.

(i) $P(W=1)$ by the Law of Total Probability

$P(W{=}1) = P(W{=}1\mid R{=}1)P(R{=}1) + P(W{=}1\mid R{=}0)P(R{=}0)$

$= (0.9)(0.3) + (0.2)(0.7) = 0.27+0.14 = 0.41$

(ii) $P(R=1 \mid W=1)$ by Bayes' Theorem

$P(R{=}1\mid W{=}1) = \frac{P(W{=}1\mid R{=}1)P(R{=}1)}{P(W{=}1)}$

$P(R{=}1\mid W{=}1) = \frac{0.27}{0.41} \approx 0.6585$

(b) Two-Step Markov State Distribution

$P = \begin{pmatrix}0.7 & 0.3\\ 0.5 & 0.5\end{pmatrix}$, $x^{(0)} = [1\ \ 0]$.

$x^{(1)} = x^{(0)}P = [0.7,\ 0.3]$

$x^{(2)} = x^{(1)}P = [0.7(0.7)+0.3(0.5),\ \ 0.7(0.3)+0.3(0.5)] = [0.64,\ 0.36]$

(c) Stationary Distribution

$P = \begin{pmatrix}0.85 & 0.15\\ 0.40 & 0.60\end{pmatrix}$.

(i) System of Equations

$q_1 = 0.85q_1 + 0.40q_2, \qquad q_2 = 0.15q_1+0.60q_2, \qquad q_1+q_2=1$

(ii) Solve

From the first equation: $0.15q_1 = 0.40q_2 \Rightarrow q_1 = \dfrac{8}{3}q_2$. Substituting into $q_1+q_2=1$:

$\frac{8}{3}q_2 + q_2 = 1 \Rightarrow \frac{11}{3}q_2=1 \Rightarrow q_2 = \frac{3}{11},\quad q_1=\frac{8}{11}$

(iii) Interpretation

Regardless of the starting state, in the long run the chain spends about $72.7\%$ of its time in $S_1$ and $27.3\%$ in $S_2$ — the process converges to this fixed distribution.

(d) Home/Office Markov Chain

Home→Office probability $=0.7 \Rightarrow$ Home→Home $=0.3$. Office→Home probability $=0.8 \Rightarrow$ Office→Office $=0.2$.

(i) Transition Matrix

$P = \begin{pmatrix} & H & O \\ H & 0.3 & 0.7\\ O & 0.8 & 0.2 \end{pmatrix}$

(ii) $P(\text{home after 2 days} \mid \text{home today})$

$x^{(0)}=[1,0] \Rightarrow x^{(1)}=[0.3,0.7] \Rightarrow x^{(2)} = [0.3(0.3)+0.7(0.8),\ 0.3(0.7)+0.7(0.2)] = [0.65,\ 0.35]$

(iii) $P(\text{office after 3 days} \mid \text{office today})$

$x^{(0)}=[0,1] \Rightarrow x^{(1)}=[0.8,0.2] \Rightarrow x^{(2)}=[0.40,0.60] \Rightarrow x^{(3)}=[0.60,\ 0.40]$

Question 5 — Binomial Theorem and Combinatorics

(a) Vandermonde's Identity

Claim: $\displaystyle\binom{m+n}{r} = \sum_{k=0}^{r}\binom{m}{r-k}\binom{n}{k}$.

Combinatorial proof. $\dbinom{m+n}{r}$ counts the ways to choose an $r$-element subset from a combined pool of $m+n$ objects, split into a group of $m$ "type-M" objects and $n$ "type-N" objects. Any such subset contains some number $k$ of type-N objects ($0 \le k \le r$) and the remaining $r-k$ from type-M. For each fixed $k$, the number of ways is $\dbinom{m}{r-k}\dbinom{n}{k}$. Summing over all possible $k$ (a partition of the count by the disjoint cases $k=0,1,\dots,r$) gives every $r$-subset exactly once:

$\binom{m+n}{r} = \sum_{k=0}^{r}\binom{m}{r-k}\binom{n}{k} \qquad \blacksquare$

(b) Coefficient of $x^4$ in $(4-x^2)^6\left(3x^2-\frac12\right)$

Step 1: General Term of $(4-x^2)^6$

$(4-x^2)^6 = \sum_{j=0}^{6}\binom{6}{j}4^{6-j}(-1)^j x^{2j}$

Step 2: Find Which $j$ Contribute to $x^4$

Multiplying by $3x^2$: need $2j+2=4 \Rightarrow j=1$. Multiplying by $-\frac12$: need $2j=4 \Rightarrow j=2$.

Step 3: Compute Each Contribution

$j=1$ term: $\dbinom{6}{1}4^5(-1)^1 = 6(1024)(-1) = -6144$; times $3$ gives $-18432$.

$j=2$ term: $\dbinom{6}{2}4^4(-1)^2 = 15(256)(1) = 3840$; times $-\frac12$ gives $-1920$.

(c) Find $n$ and $k$ from $(1+kx)^n = 1+8x+42x^2+\cdots$

Step 1: Match the First Two Terms

$(1+kx)^n = 1 + nkx + \binom{n}{2}k^2x^2 + \cdots$

$nk = 8 \qquad \text{...(1)}$

$\frac{n(n-1)}{2}k^2 = 42 \ \Rightarrow\ n(n-1)k^2 = 84 \qquad \text{...(2)}$

Step 2: Solve Simultaneously

Substitute $k = 8/n$ from (1) into (2):

$n(n-1)\cdot\frac{64}{n^2} = 84 \ \Rightarrow\ \frac{64(n-1)}{n} = 84 \ \Rightarrow\ 64n-64 = 84n \ \Rightarrow\ n = -\frac{16}{5}$

$k = \frac{8}{n} = \frac{8}{-16/5} = -\frac52$

Verification

$nk = (-\tfrac{16}{5})(-\tfrac52)=8$ ✓. $\dbinom{n}{2}k^2 = \dfrac{n(n-1)}{2}k^2 = \dfrac{(-16/5)(-21/5)}{2}\cdot\dfrac{25}{4} = \dfrac{336/25}{2}\cdot\dfrac{25}{4}=42$ ✓.

(d) Coefficient of $x^{-2}$ in $6x^4\left(3x-\dfrac{q}{x^2}\right)^6$

Step 1: General Term

$\binom{6}{j}(3x)^{6-j}\left(-\frac{q}{x^2}\right)^{j} = \binom{6}{j}3^{6-j}(-q)^j\, x^{6-3j}$

Multiplying by the outer $6x^4$, the exponent of $x$ becomes $10-3j$.

Step 2: Match the Target Exponent

$10 - 3j = -2 \ \Rightarrow\ j = 4$

Step 3: Coefficient in Terms of $q$

$6\binom{6}{4}3^{2}(-q)^4 = 6(15)(9)q^4 = 810\,q^4$

Setting this equal to the given value $(-540)^2 = 291600$:

$810\,q^4 = 291600 \ \Rightarrow\ q^4 = 360 \ \Rightarrow\ q = \pm\sqrt[4]{360} \approx \pm 4.357$

Question 6 — Calculus, Gradient Descent, and Lagrange Multipliers

(a) Derivative from First Principles

Start from the average rate of change of $f$ over $[x, x+h]$:

$\text{Average rate of change} = \frac{f(x+h)-f(x)}{h}$

The instantaneous rate of change — the derivative — is what this average approaches as the interval shrinks to a point, i.e. as $h \to 0$:

$f'(x) = \lim_{h\to 0}\frac{f(x+h)-f(x)}{h}$

(b) One Step of Gradient Descent on $f(x,y)=x^2+4y^2$

(i) Update Rule

$\begin{pmatrix}x_{k+1}\\ y_{k+1}\end{pmatrix} = \begin{pmatrix}x_k\\ y_k\end{pmatrix} - \alpha \nabla f(x_k,y_k), \qquad \nabla f(x,y) = \begin{pmatrix}2x\\ 8y\end{pmatrix}$

(ii) One Iteration from $(x_0,y_0)=(1,1)$, $\alpha=0.1$

$\nabla f(1,1) = (2,8)$

$(x_1,y_1) = (1,1) - 0.1(2,8) = (1-0.2,\ 1-0.8) = (0.8,\ 0.2)$

(c) Constrained Minimization with Lagrange Multipliers

Minimize $f(x,y)=x^2+4y^2$ subject to $g(x,y)=x+y-1=0$.

(i) Lagrangian

$\mathcal{L}(x,y,\lambda) = x^2+4y^2 - \lambda(x+y-1)$

(ii) System of Equations

$\frac{\partial \mathcal{L}}{\partial x} = 2x-\lambda = 0, \qquad \frac{\partial \mathcal{L}}{\partial y} = 8y-\lambda=0, \qquad \frac{\partial \mathcal{L}}{\partial \lambda} = -(x+y-1)=0$

(iii) Solve for the Critical Point

From the first two equations: $\lambda=2x=8y \Rightarrow x=4y$. Substituting into $x+y=1$: $4y+y=1 \Rightarrow y=\dfrac15,\ x=\dfrac45$.

Question 7 — Markov Chain Theory and Application

(a) Definition and Types of States

A Markov chain is a stochastic process $\{X_n\}$ over a discrete state space where the future state depends only on the present state, not on the full history — the Markov property:

$P(X_{n+1}=j \mid X_n=i, X_{n-1}, \dots, X_0) = P(X_{n+1}=j\mid X_n=i)$

(b) Transition Probability and Transition Probability Matrix

The transition probability $p_{ij} = P(X_{n+1}=j \mid X_n=i)$ is the chance of moving from state $i$ to state $j$ in one step. Collecting all $p_{ij}$ into a matrix $P = [p_{ij}]$ (rows summing to $1$) gives the transition probability matrix.

Example: for the home/office chain in part (c), $P = \begin{pmatrix}0.3 & 0.7\\ 0.8 & 0.2\end{pmatrix}$ — row $H$ says "$30\%$ stay home, $70\%$ go to office tomorrow."

(c) Home/Office Chain (same setup as Question 4(d))

$P = \begin{pmatrix}0.3 & 0.7\\ 0.8 & 0.2\end{pmatrix}$

$x^{(0)}=[1,0]\ \Rightarrow\ x^{(2)}=[0.65,\ 0.35] \qquad\qquad x^{(0)}=[0,1]\ \Rightarrow\ x^{(3)}=[0.60,\ 0.40]$

Question 8 — Sampling, Confidence Intervals, and Hypothesis Testing

(a) Sampling Methods (selecting 100 of 1000 students)

(b) 95% Confidence Interval for the Mean

Given: $n=36,\ \bar{x}=70,\ \sigma=12$.

Step 1: Standard Error

$SE = \frac{\sigma}{\sqrt{n}} = \frac{12}{\sqrt{36}} = \frac{12}{6} = 2$

Step 2: Critical $z$-value

From the table, $95\% \Rightarrow z_c = 1.96$.

Step 3: Confidence Interval

$\bar{x} \pm z_c \cdot SE$

$70 \pm 1.96(2) = 70 \pm 3.92$

(c) Hypothesis Test for $\mu = 75$

(i) Hypotheses

$H_0: \mu = 75 \qquad H_1: \mu \ne 75 \quad \text{(two-tailed)}$

(ii) Test Statistic

$z = \frac{\bar{x}-\mu_0}{SE} = \frac{70-75}{2} = -2.5$

(iii) p-value Decision

From the $z$-table, $\Phi(2.5) = 0.9938$, so

$p = 2\bigl(1-\Phi(2.5)\bigr) = 2(1-0.9938) = 2(0.0062) = 0.0124$

Since $p = 0.0124 < \alpha = 0.05$, reject $H_0$.

Interview Corner