# Use “strong” mathematical induction to verify an explicit formula for the given sequence

This is a "study guide" question for a test I am trying to figure out. The sequence given is

$a_k=\dfrac{2}{a_{k-1}}$ for all integers $k\ge2$, and $a_1=1$.

It then asks me to find an explicit formula and prove it with "strong" induction. I came up with the following explicit formula:

$a_k=\dfrac{(-1)^k+3}{2}$

But I have no idea how to implement the proof of this. I understand that strong induction is like a normal mathematical induction proof but instead of proving for $k+1$ I need to prove for a range? I'm just not sure what my inductive hypothesis and base cases are for this problem. Thanks for any help!

-
Just use "normal" induction. Strong induction for one proposition is just normal induction for a modified proposition anyway. –  Hagen von Eitzen Oct 27 '12 at 6:44
Well the reason I'm trying to use strong induction is because it says to in the problem - but I have no idea how to apply it to this. –  Jon Oct 27 '12 at 7:01
Then the problem is stupid. There is no reason to use strong induction here. –  Chris Eagle Oct 27 '12 at 7:42
You came up with this formula? The formulas one can come up with when fiddling with the definition, trying some cases and the like, are more likely to resemble $a_{2k}=2$, $a_{2k+1}=1$. –  Did Oct 27 '12 at 8:50
@did: What you describe would be considered by many not to constitute a formula. Quite possibly OP did find this description and then came up with the mentioned formula. –  Marc van Leeuwen Oct 27 '12 at 8:56

You need only ordinary induction, and you don’t need to split it into two cases: if $a_k=\dfrac{(-1)^k+3}2$, then

$$\frac2{a_k}=\frac4{(-1)^k+3}\cdot\frac{(-1)^k-3}{(-1)^k-3}=\frac{4\left((-1)^k-3\right)}{-8}=\frac{-\left((-1)^k-3\right)}2=\frac{(-1)^{k+1}+3}2\;.$$

Added: I forgot to mention that with initial datum $a_1=1$ the problem is trivial. Let $f(x)=\frac2x$, so that $a_{k+1}=f(a_k)$ for all $k\ge 1$, and note that $f(1)=2$ and $f(2)=1$, which immediately proves the closed form

$$a_k=\begin{cases}1,&\text{if }k\text{ is odd}\\2,&\text{if }k\text{ is even}\;.\end{cases}$$

-
It's trivial whatever the (non-zero) value of $a_1$, because $2/(2/a_1) = a_1$. –  TonyK Oct 27 '12 at 9:00
@TonyK: True. I expressed myself poorly: I meant that the triviality is especially obvious, because the numbers are so nice. –  Brian M. Scott Oct 27 '12 at 9:08
That's how I was thinking about it, couldn't figure out how to apply "strong" induction. Since this seems to be the consensus I just won't spend too much more time thinking about this one :) –  Jon Oct 28 '12 at 6:21

I think just distinguish the case for odd and even $k$, then you can prove that using normal induction.

-
That makes sense I guess. Seems kinda pointless to me. –  Jon Oct 27 '12 at 7:37
Actually this series is periodic as 1, 2, 1, 2.... So all you have to prove is when we have 1 at current position, the next element should be 2, and if we have 2 at current position, the next element should be 1, which is trivial from the recurrence formula. –  user46090 Oct 27 '12 at 8:36