proof by induction with inequalities

**narjsingh** · October 11th 2012, 05:33 AM

question is prove by induction on m that m^3 <= 2^m for m=>10
thats supposed to be m cube less than or equal to 2 to the power n for m greater than or equal to 10

P(K)= k^3 less than or equal to 2^k
P(K+1)= (k+1)^3 less than or equal to 2^k+1

2k^3 less than or equal to 2^k+1

(k+1)^3 less than or equal to 2k^3
now im not sure to do next
please help

**emakarov** · October 11th 2012, 05:57 AM

$\begin{align*} (k+1)^3&=k^3+3k^2+3k+1\\ &\le k^3+3k^2+3k^2+k^2&& \text{since }k\ge3 \\&=k^3+7k^2\\&\le k^3+k^3&& \mbox{since }k\ge7\\&\le2^k+2^k&& \text{by induction hypothesis}\\&=2^{k+1}\end{align*}$

A couple of remarks. For each claim it should be clear whether you are assuming it, trying to prove it or something else. Your proof is just a series of statements, and the role of those statements is not clear. Write comments when necessary, such as "We assume ...," "We need to prove ...," "It follows from ... that ..."

Mathematics is case-sensitive, so K and k may denote different variables.

Edit: Don't forget the base case.

**narjsingh** · October 12th 2012, 01:10 PM

Originally Posted by emakarov

$\begin{align*} (k+1)^3&=k^3+3k^2+3k+1\\ &\le k^3+3k^2+3k^2+k^2&& \text{since }k\ge3 \\&=k^3+7k^2\\&\le k^3+k^3&& \mbox{since }k\ge7\\&\le2^k+2^k&& \text{by induction hypothesis}\\&=2^{k+1}\end{align*}$

thanks but i dont understand where the second line has come from, how did you get k^3+3k^2+3k^2+k^2

**Plato** · October 12th 2012, 01:30 PM

Originally Posted by narjsingh

thanks but i dont understand where the second line has come from, how did you get k^3+3k^2+3k^2+k^2

$1\le k^2$

**narjsingh** · October 12th 2012, 01:39 PM

Originally Posted by Plato

$1\le k^2$

im really really sorry i still dont get that im a bsc econ student

**Plato** · October 12th 2012, 01:51 PM

Originally Posted by narjsingh

im really really sorry i still dont get that im a bsc econ student

Because $k\le k^2~\&~1\le k^2$ we get $3k+1\le 3k^2+k^2$

$k^3+3k^2+3k+1\le k^3+3k^2+3k^2+k^2$

**narjsingh** · October 12th 2012, 01:59 PM

Originally Posted by Plato

Because $k\le k^2~\&~1\le k^2$ we get $3k+1\le 3k^2+k^2$

$k^3+3k^2+3k+1\le k^3+3k^2+3k^2+k^2$

thank you so much! i am really getting it! one last hing how did you get k is greater than or equal to 7?

**Plato** · October 12th 2012, 02:08 PM

Originally Posted by narjsingh

thank you so much! i am really getting it! one last hing how did you get k is greater than or equal to 7?

$3+3+1=7$ so $3k^2+3k^2+k^2=7k^2$

Math Help - proof by induction with inequalities

LinkBack

Thread Tools

Display

proof by induction with inequalities

Re: proof by induction with inequalities

Re: proof by induction with inequalities

Re: proof by induction with inequalities

Re: proof by induction with inequalities

Re: proof by induction with inequalities

Re: proof by induction with inequalities

Re: proof by induction with inequalities

Similar Math Help Forum Discussions

Induction with Inequalities help

Proof by Induction : Inequalities

induction inequalities P1

induction inequalities P3

Induction and Inequalities

Search Tags