# Two exercises on mathematical induction

Studying for a test and can't work out how to do two questions on the sample test.

(1) Suppose a sequence of numbers $a_1$, $a_2$, $\dots$ is defined recursively by: $$a_1 = 1\qquad\text{and}\qquad a_{n+1} = \frac{a_n}{a_n + 1}$$

Prove, using mathematical induction, that for each integer $n\ge 1$

$$a_n = \frac{1}{n}.$$

(2) Using mathematical induction, prove that the formula $$g^n = \begin{pmatrix}1 & 0 \\ -2n & 1\end{pmatrix}$$ where $$g = \begin{pmatrix}1 & 0 \\ -2 & 1\end{pmatrix}$$ is correct for each integer $n \geq 1$.

If someone could show me how there done would be a big help thanks.

• I've tried to write the first question into MathJax markup in order to clarify it. For the second question it's difficult to understand what it means; what's $g$? Is the equality $g^n=\left(\begin{smallmatrix}1 & 0\\ -2n & 1\end{smallmatrix}\right)$? – egreg May 26 '13 at 9:28
• By the way, this isn't linear algebra really; the last step might involve a matrix but only trivially. – Sharkos May 26 '13 at 9:33

Hints:

$$\bullet\;\;\;\;\;\;\;\;\;\;\;\;\;a_{n+1}=\frac{a_n}{a_n+1}\stackrel{\text{Ind. Hypot.}}=\frac{\frac1n}{\frac1n+1}=\frac1{n+1}$$

Since I've no idea what $\,g\,$ is in the second question I can't help there.

• Thanks Don so much for that editing.:-) – Mikasa May 27 '13 at 2:26

Well, to prove inductively that a statement holds for all $n \geq 0$, you need to show that

1. The statement holds for $n_0$
2. Whenever the statement holds for $n \geq n_0$, it also holds for $n+1 \geq n_0$.

In your case, you thus need to show that

1. $a_1 = \frac{1}{1}$
2. If $a_n = \frac{1}{n}$ ($n \geq 1$) then $a_{n+1} = \frac{a_n}{a_n + 1} \overset{\text{?}}= \frac{1}{n+1}$.