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, 2012 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, 2012 at 7:01
  • $\begingroup$ Then the problem is stupid. There is no reason to use strong induction here. $\endgroup$
    – Chris Eagle
    Oct 27, 2012 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, 2012 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, 2012 at 8:56

2 Answers 2

Reset to default
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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 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.