Proof by Induction Watch

andrewlee89
Badges: 0
Rep:
?
#1
Report Thread starter 10 years ago
#1
Prove \displaystyle\ 3^n > 2n^2 -1 for every positive integer \displaystyle\ n

Now I've done with the basis case, but the assume n = k part. Say 3^{k+1} > 3(2k^2 -1) I can rearrange to get something like this, \displaystyle\ 3(2k^2 -1) = 6k^2 -3 = 2k^2 + 4k^2 -4 +1 = 2k^2 +4(k^2 -1) + 1 , problem is if u compare this with \displaystyle\ 2(k+1)^2 -1 and expand it, I cannot prove that \displaystyle\ k^2 -1 > k. Any ideas? I thought of taking a method of difference approach i.e \displaystyle\ 3^{n+1} - 3^n = 3^n(3 - 1) but I couldn't come up with anything. Help!
0
quote
reply
Zhen Lin
Badges: 10
Rep:
?
#2
Report 10 years ago
#2
You're supposed to prove that if 3^k > 2k^2 - 1 then 3^{k + 1} > 2(k + 1)^2 - 1.
0
quote
reply
generalebriety
Badges: 14
Rep:
?
#3
Report 10 years ago
#3
Hold on - you're trying to get (2k + 1)^2 - 1, not what you wrote. This is 4k^2 + 4k.
0
quote
reply
Zhen Lin
Badges: 10
Rep:
?
#4
Report 10 years ago
#4
Hmm, I'm not seeing a straightforward way to do this. It can be shown that 3^{k + 1} - \left(2\left(k + 1\right)^2 - 1\right) > 3\left(3^k - \left(2k^2 - 1\right)\right) - 5, but in order to complete the proof from there it would be necessary to show that 3\left(3^k - \left(2k^2 - 1\right)\right) > 5 for all positive integers k... There's probably an easier way I'm not thinking of.
0
quote
reply
DFranklin
Badges: 18
Rep:
?
#5
Report 10 years ago
#5
One way:

From 3^n > 2n^2 - 1 we get

3^(n+1) > 3(2n^2-1). Then consider 3(2n^2-1)-(2(n+1)^2-1) and show it's > 0 for n > 1.
0
quote
reply
Zhen Lin
Badges: 10
Rep:
?
#6
Report 10 years ago
#6
Ah, of course. I did that but when the completed-square form came out as (2n - 1)^2 - 5 I thought I was going the wrong way, since I thought the condition required was > 0 for n \ge 1.
0
quote
reply
DFranklin
Badges: 18
Rep:
?
#7
Report 10 years ago
#7
In these cases, never forget you don't have to start from n = 1. If you end up only being able to show 3^n > 2n^2 - 1 \implies 3^{n+1} > 2(n+1)^2 - 1 for n > 3, there's nothing stopping you checking explicitly for n = 1, 2, 3, 4.

It's not uncommon to have to do this sort of thing for real problems: Bertrand's postulate says that there's always a prime between n and 2n. One proof shows analytically that there's always a prime between n and 2n for n >= 512. Then the proof for n < 512 is done by direct calculation.
0
quote
reply
X

Reply to thread

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • University of Lincoln
    Brayford Campus Undergraduate
    Wed, 12 Dec '18
  • Bournemouth University
    Midwifery Open Day at Portsmouth Campus Undergraduate
    Wed, 12 Dec '18
  • Buckinghamshire New University
    All undergraduate Undergraduate
    Wed, 12 Dec '18

Do you like exams?

Yes (166)
18.57%
No (543)
60.74%
Not really bothered about them (185)
20.69%

Watched Threads

View All