
Algebra PreAlgebra and Basic Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
October 6th, 2017, 08:52 AM  #1 
Member Joined: Sep 2014 From: Sweden Posts: 71 Thanks: 0  Mathematical Induction: Prove that n^2 < 2^n then n > 4
I am struggling with mathematical induction and have watched a lot of videos on youtube about it but still doesn't really get it. The first step is clear but the second isn't. According to a PDFfile from my highschool I'm supposed to follow these steps: $\displaystyle \displaystyle P(1) \ \ \ \ (\ P(5) \ in \ this \ case, \ i \ guess\ )\\\\ \displaystyle \forall n \in \mathbb{N} : P(n) \Rightarrow P(n+1)\\\\ \displaystyle \forall n \in \mathbb{N} : P(n)\\\\ $ The assignment I have is: Show that $\displaystyle \displaystyle n^2 < 2^n$ then $\displaystyle n > 4$ (1) Assume that P(5) is true and prove that it is true $\displaystyle \displaystyle Assume \ that \ P(5) \ is \ true\\\\ \displaystyle P(5) = 5^2 < 2^5 = 25 < 32 \ true\\\\ \displaystyle P(n) \Rightarrow P(n+1)\\\\ \displaystyle P(n+1)=(n+1)^2<2^{n+1}\\\\ \displaystyle =(n+1)^2<2^n \cdot 2^1\\\\ $ And from here I don't get any further . . . Last edited by DecoratorFawn82; October 6th, 2017 at 09:03 AM. 
October 6th, 2017, 09:31 AM  #2 
Global Moderator Joined: May 2007 Posts: 6,397 Thanks: 546 
$\displaystyle (n+1)^2=n^2+2n+1,\ n^2<2^n,\ 2n+1<n^2$ Consolidate to get desired result. 
October 6th, 2017, 09:47 AM  #3 
Member Joined: Sep 2014 From: Sweden Posts: 71 Thanks: 0 
How can you know that $\displaystyle \displaystyle 2n+1 < n^2$? I get that $\displaystyle (n+1)^2 = n^2+2n+1$ But the following lines below can't be equal? So where does the second line come from? $\displaystyle (n+1)^2<2^n \cdot 2^1 =$ $\displaystyle 2n+1<n^2$ I'm just a little confused what's happening in all the steps. Last edited by DecoratorFawn82; October 6th, 2017 at 09:49 AM. 
October 6th, 2017, 11:56 AM  #4 
Global Moderator Joined: Dec 2006 Posts: 18,243 Thanks: 1439 
Let $P(n)$ be the proposition that $n^2 < 2^n$ for $n > 4$, where $n \in \mathbb{N}$. As $5^2 < 2^5, \,P(5)$ is true. If $k > 4$ and $P(k)$ is true, $k^2 < 2^k$. Also, $2k + 1 < 2k + 3 + (k  3)(k + 1) = k^2$, so $2k + 1 < 2^k$. Hence $(k + 1)^2 = k^2 + 2k + 1 < 2^k + 2^k = 2^{k+1}$, i.e. $P(k + 1)$ is true. By induction, $P(n)$ is always true. The proposition given in the title is slightly different, and untrue for n = 1. 
October 7th, 2017, 04:26 AM  #5 
Math Team Joined: Jan 2015 From: Alabama Posts: 2,875 Thanks: 766 
You have "The assignment I have is: Show that $\displaystyle n^2< 2^n$ then n> 4" I presume you mean "Show that $\displaystyle n^2< 2^n$ when n> 4". 

Tags 
<, >, <, induction, mathematical, prove 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
how to prove this without mathematical induction  numeriprimi  Elementary Math  2  September 30th, 2017 12:28 PM 
How to prove this by mathematical induction?  mitch08  Computer Science  1  October 4th, 2015 09:39 PM 
Prove using mathematical induction  wannabemathlete  Algebra  4  October 23rd, 2014 11:01 PM 
Prove with mathematical induction  Phatossi  Algebra  4  November 10th, 2012 06:27 PM 
How to prove this by mathematical induction?  hs_pec  Calculus  0  December 31st, 1969 04:00 PM 