Showing a sequence converges to 0

[trap101]

Show that 2^n/n! Converges to 0 by showing that 2^n/n! <= 4/n
My problem is in showing 2^n/n! <= 4/n

I know 4/n goez to 0, but how to get the inequality to be true? Doing some rough work I noticed that it "appears" to be true for n>=3. Would induction be the way to go about this step? Because nothing else is I am thinking of is coming close to a full thought.

 

[disregardthat]

Yes, try induction.

 

[trap101]

I am actually having a little problem with the induction.

Assuming all the base case steps are done and we are assuming 2^k/k! <= 4/(k) is true:

2^(k+1)/(k+1)! <= 4/(k+1) [trying to prove]

I am trying to fiddle with it, but nothing much has come up as constructive.

Perhaps: 4/(k+1) = 2 [2/(k+1)] > 2/(K+1), But I am still left trying to show 2/(k+1) > 2^(k+1)/(k+1)!

 

[disregardthat]

Tip: factor out 2^k/k! out of 2^(k+1)/(k+1)! and use the inductive hypothesis.

 

[trap101]

I tried that before and got

(2^k/k!)(2/(k+1)) <= (4/k)(2/(k+1))

Now by inductive hypothesis I know already that (2^k/k!) <= (4/k), and just multiplying both sides of that doesn't change that, but I feel I still need to have 4/(k+1) to appear in the inequality somewhere.

 

[disregardthat]

You have this

(2^k/k!)(2/(k+1)) <= (4/k)(2/(k+1))

so it suffices to prove that

(4/k)(2/(k+1)) <= 4/(k+1)

 

[pasmith]

I tried that before and got

(2^k/k!)(2/(k+1)) <= (4/k)(2/(k+1))

Now by inductive hypothesis I know already that (2^k/k!) <= (4/k), and just multiplying both sides of that doesn't change that, but I feel I still need to have 4/(k+1) to appear in the inequality somewhere.

By the magic of commutativity of multiplication,
$$\frac{2}{k + 1} \frac{4}{k} = \frac{2}{k} \frac{4}{k + 1}.$$ What condition must 2/k satisfy if this is to be less than or equal to 4/(k + 1)?

 

[skiller]

I think I may be showing my inexperience here, but I'm struggling to see how the other posts are helping (although I'm sure they will be doing just that!).

But personally, my thoughts on it are:

Assuming all the base case steps are done and we are assuming 2^k/k! <= 4/(k) is true:

2^(k+1)/(k+1)! <= 4/(k+1) [trying to prove]

...you have started by stating what you need to prove. Surely you should be stating what you know to be true (given the assumption) and then deducing what you need to prove.

 

[trap101]

You have this

(2^k/k!)(2/(k+1)) <= (4/k)(2/(k+1))

so it suffices to prove that

(4/k)(2/(k+1)) <= 4/(k+1)

Bloody hell, that's what I was missing to do, I've been trying to polish up on these processes for the new year. So now there is no factorial which makes it a lot easier. Of course it would be induction again on this piece correct, but no factorial should make it more straight forward. If I have an issue I will ask for help. Thanks

 

[trap101]

By the magic of commutativity of multiplication,
$$\frac{2}{k + 1} \frac{4}{k} = \frac{2}{k} \frac{4}{k + 1}.$$ What condition must 2/k satisfy if this is to be less than or equal to 4/(k + 1)?

Ok so I thought I had it figured out, but apparently not. So moving along we've established that it suffices to show that (4/k)(2/(k+1)) <= 4/(k+1) and I will be done.

So going with the hint from pasmith I found that if 2 <= K then this inequality will hold. But I feel I am still missing something in terms of induction. Don't I have to find a middle value of some sort between (4/k)(2/(k+1)) and 4/(k+1) that I could use to show that it (4/k)(2/(k+1)) is less than 4/(k+1) ?

 

[pasmith]

Ok so I thought I had it figured out, but apparently not. So moving along we've established that it suffices to show that (4/k)(2/(k+1)) <= 4/(k+1) and I will be done.

So going with the hint from pasmith I found that if 2 <= K then this inequality will hold. But I feel I am still missing something in terms of induction. Don't I have to find a middle value of some sort between (4/k)(2/(k+1)) and 4/(k+1) that I could use to show that it (4/k)(2/(k+1)) is less than 4/(k+1) ?

You want to show that $0 < x < y$. You know that $x = ay$ where $0 < a < 1$. But that's sufficient because, by an axiom of the rational number system, if $a < 1$ then multiplying both sides by the positive number $y$ will preserve the inequality: $ay < y$.

Thus it is enough to note that $2/k \leq 1$ when $k \geq 2$, which $k$ is because $k$ is a positive integer and you aren't using this argument to establish the base case $k = 1$; you will do that by direct substitution.

 

[trap101]

Ok so if I may summarize to make sure I got the thinking right.

So at our inductive we assumed that 2^k/k! <= 4/k.

decomposing 2^(k+1)/(k+1)! = (2^k/k!)(2/(k+1))

so this provides me with the hint that I multiply both sides of 2^k/k! <= 4/k by (2/(k+1))

now since by assumption we know 2^k/k! <= 4/k is true, multiplying the same value on both sides does not affect it, which leaves me with showing that if (4/k)(2/(k+1)) <= 4/(k+1) is true, then I have established the result.

Now after some work (4/k)(2/(k+1)) <= 4/(k+1) is true as long as K >= 2 because by the commutativity of multiplication: (4/k)(2/(k+1)) = (2/k)(4/(k+1)) and as long as 2/k <= 1 this will be the case. Since we are showing that this holds for all positive integers and this statement is true for k >= 2, then we have established that (4/k)(2/(k+1)) <= 4/(k+1) and the result follows.

 

[disregardthat]

Note here that you are required to verify this for n = 1 AND n = 2 for the inductive step to hold. Part of the assumption must be that k >= 2, which means that the case n = 2 must be part of the base case.

 

[trap101]

Got it. Thanks all for the help.

 

[skiller]

You want to show that $0 < x < y$. You know that $x = ay$ where $0 < a < 1$. But that's sufficient because, by an axiom of the rational number system, if $a < 1$ then multiplying both sides by the positive number $y$ will preserve the inequality: $ay < y$.

Thanks. Good to know. This is exactly what I was trying to hint at in post #8. Still not fully understanding your post #7 though!

Note here that you are required to verify this for n = 1 AND n = 2 for the inductive step to hold. Part of the assumption must be that k >= 2, which means that the case n = 2 must be part of the base case.

No, not getting this at all. Why must n=2 be part of the base assumption?

The statement is true when n=1 (true for n=0, in fact - not sure I would reach out for n<0 as I'm not too clear on negative factorials just yet - I'm only in my 40s and not reached that part of my study just yet!), and it can be proved for all integer k+1 if we assume true for any integer k. Therefore the direct proof of case k=2 isn't necessary at all. Of course, proving that the case n=2 is true could be put forward as part of your base assumption, as, well, yes, it's obviously true! But not a necessary assumption.

If this isn't the case then either I need to go back and study maths, or have a long lie down.

 

[disregardthat]

You have proven that the statement, call it $P(n)$, is such that *) $P(k) \Rightarrow P(k+1)$ for $k \geq 2$. If you initially show $P(1)$, and then the chain of implications $P(2) \Rightarrow P(3) \Rightarrow P(4) \Rightarrow ...$ which is what *) basically says, then you can never make the leap from $P(1)$ to $P(2)$. You need to know $P(2)$ in order to conclude with $P(3)$, and then $P(4)$, and so on...