# Prove by induction

1. Nov 11, 2005

### symplectic_manifold

Hello!
We've got the following to prove by induction:
a) $2n+1\le{2^n}$
b) $n^2\le{2^n}$
(It is assumed that 0 is a natural number)

a) This inequality is not valid for $n=1,2$, so to prove the inequality one has to show its validity for all $n\ge{3}$:
1) $A(3):7\le{8}$ (true)
2) Assume that $A(n)$ is true.
$A(n+1): 2(n+1)+1\le{2^{n+1}}$
$2(n+1)+1=(2n+1)+2\le{2^n+2}\le{2^{n+1}}$, since for $2^n+2\le{2^{n+1}}$ we have $n\ge{1}$

Is there a difference if I make the induction step this way?:
2)$A(n+1): 2(2n+1)\le{2^{n+1}}$, so to prove A(n) we must show that $2n+3\le{4n+2}$, which is also true for $n\ge{1}$
The thing that disturbs me is that if we assume 0 to be a natural number the last inequalities in 2) in both cases do not hold...but I think this case doesn't play a role since we are to prove it for n greater 3...does it?

b) This inequality is invalid for all $n=3$, so to show that the inequality is valid we must show that it is valid for all $n\ge{4}$
1) $A(4)=16\le{16}$ (true)
2) Assume that $A(n)$ is true.
$A(n+1): (n+1)^2\le{2^{n+1}}$
$(n+1)^2=n^2+2n+1\le{2^n+2n+1}\le{2^{n+1}}$. The last inequality in this string is equivalent to $2n+1\le{2^n}$, which was proved in a).

Here, equally, the same question...Is there a difference if I do it this way?:
2) $A(n+1): 2n^2\le{2^{n+1}}$
$(n+1)^2=n^2+2n+1\le{n^2+3n-3}\le{n^2+n^2-3}\le{2n^2}$

Last edited: Nov 11, 2005
2. Nov 11, 2005

### matt grime

but, you need to work on your method of proof and its exposition. it is not clear at all what you think you have shown and why that proves the result.

2. can be done if we can show (n+1)^2 <2n^2 for then (n+1)^2 <2n^2 < 2.2^n (inductively) =2^(n+1)

so prove that (n+1)^2 <2n^2 for all n sufficiently large.

3. Nov 11, 2005

### symplectic_manifold

Induction/Sum

$\sum_{k=0}^{n}\frac{1}{k!}<3$
1) A(0): 1<3 (true);
2) Given A(n) then A(n+1):
$\sum_{k=0}^{n+1}\frac{1}{k!}<3\Leftrightarrow{\sum_{k=0}^{n}\frac{1}{k!}+\frac{1}{(n+1)!}<3}\Leftrightarrow{\sum_{k=0}^{n}\frac{1}{3k!}+\frac{1}{3(n+1)!}<1}$
So to prove it we must show that $\frac{1}{3(n+1)!}<1$, which is straightforward because $3(n+1)!>1$ for all n, and at the same time $\sum_{k=0}^{n}\frac{1}{k!}>\frac{1}{(n+1)!}$. The last inequality is pretty clear but how to prove it? Is it because of the fact that $2(n+1)!>1$ and $\frac{(n+1)!}{n!}\ge{1}$, so that $\sum_{k=0}^{n}\frac{1}{k!}>{\frac{1}{(n+1)!} \Leftrightarrow{2(n+1)!+\sum_{k=2}^{n}\frac{(k+1)!}{k!}>1}$ for all n?
I'm not sure whether it is enough.

Last edited: Nov 11, 2005
4. Nov 11, 2005

### matt grime

again you're starting from the answer you want to prove this is bad.

no, that will not suffice to prove it, and doesn't help.

In anycase, this can be done easily without induction (i don't even see an obvious inductive proof) since

1+1+1/2+1/3!+1/4!...

is strictly bounded above by

1+1+1/2+...

where you should make the ... into a series you can easily sum

oh, may be i do see an inductive proof. start with the expression for the sum to n+1 (and DO NOT say it is less than 3) and manipulate it

Last edited: Nov 11, 2005