My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Thanks Tree2Thanks
  • 2 Post By skipjack
Reply
 
LinkBack Thread Tools Display Modes
October 6th, 2017, 07:52 AM   #1
Member
 
Joined: Sep 2014
From: Sweden

Posts: 67
Thanks: 0

Question 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 PDF-file 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 08:03 AM.
DecoratorFawn82 is offline  
 
October 6th, 2017, 08:31 AM   #2
Global Moderator
 
Joined: May 2007

Posts: 6,341
Thanks: 532

$\displaystyle (n+1)^2=n^2+2n+1,\ n^2<2^n,\ 2n+1<n^2$

Consolidate to get desired result.
mathman is offline  
October 6th, 2017, 08:47 AM   #3
Member
 
Joined: Sep 2014
From: Sweden

Posts: 67
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 08:49 AM.
DecoratorFawn82 is offline  
October 6th, 2017, 10:56 AM   #4
Global Moderator
 
Joined: Dec 2006

Posts: 18,036
Thanks: 1394

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.
Thanks from greg1313 and DecoratorFawn82
skipjack is online now  
October 7th, 2017, 03:26 AM   #5
Math Team
 
Joined: Jan 2015
From: Alabama

Posts: 2,719
Thanks: 699

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".
Country Boy is offline  
Reply

  My Math Forum > High School Math Forum > Algebra

Tags
&lt, >, <, 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 11:28 AM
How to prove this by mathematical induction? mitch08 Computer Science 1 October 4th, 2015 08:39 PM
Prove using mathematical induction wannabemathlete Algebra 4 October 23rd, 2014 10:01 PM
Prove with mathematical induction Phatossi Algebra 4 November 10th, 2012 05:27 PM
How to prove this by mathematical induction? hs_pec Calculus 0 December 31st, 1969 04:00 PM





Copyright © 2017 My Math Forum. All rights reserved.