1
$\begingroup$

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!

$\endgroup$
7
  • 1
    $\begingroup$ Just use "normal" induction. Strong induction for one proposition is just normal induction for a modified proposition anyway. $\endgroup$ – Hagen von Eitzen Oct 27 '12 at 6:44
  • $\begingroup$ 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. $\endgroup$ – Jon Oct 27 '12 at 7:01
  • $\begingroup$ Then the problem is stupid. There is no reason to use strong induction here. $\endgroup$ – Chris Eagle Oct 27 '12 at 7:42
  • $\begingroup$ 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$. $\endgroup$ – Did Oct 27 '12 at 8:50
  • $\begingroup$ @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. $\endgroup$ – Marc van Leeuwen Oct 27 '12 at 8:56
1
$\begingroup$

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}$$

$\endgroup$
3
  • 1
    $\begingroup$ It's trivial whatever the (non-zero) value of $a_1$, because $2/(2/a_1) = a_1$. $\endgroup$ – TonyK Oct 27 '12 at 9:00
  • $\begingroup$ @TonyK: True. I expressed myself poorly: I meant that the triviality is especially obvious, because the numbers are so nice. $\endgroup$ – Brian M. Scott Oct 27 '12 at 9:08
  • $\begingroup$ 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 :) $\endgroup$ – Jon Oct 28 '12 at 6:21
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ That makes sense I guess. Seems kinda pointless to me. $\endgroup$ – Jon Oct 27 '12 at 7:37
  • $\begingroup$ 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. $\endgroup$ – AmFCG Oct 27 '12 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.