You are not logged in.
Pages: 1
Hello!
Quick background on the newbie...I'm a junior at eastern Connecticut State University studying to be a secondary mathematics educator...so I'm working on my undergrad degree in math. Always thought I was pretty good at math, has always been my strongest subject and I have an eye, memory, and understanding of numbers. However, I'm in a Discrete Structures course with a terrible instructor and I'm stuck. We're going over proofs using the Principle of Mathematical Induction (PMI) and I understand the concept. I had a problem getting through a proof (the 2nd one below), but in typing it I figured it out. However, it seems like there has to be an easier way to do it...any chance someone can guide me where I need to go?
The first example we had to prove was 2+4+6...+2n=n(n+1)
Simple enough...basis step yields 2=2(2)=2(2+1) => 6=6 => true
Inductive step assumes 2+4+6...+2k=k(k+1) is true and then finally we arrive at 2+4+6...+2k+(2k+1)=(k+1)(k+2)
Substituting k(k+1) for {2+4+6...+k} nets k(k+1)+(2k+1)=(k+1)(k+2)...both sides simplify to k²+3k+2, so the proof is complete
Now...next problem that we run into is more involved...
We have a 2 part formula:
c sub 1 = 0
c sub n = c sub (floor [n/2]) + n² for all x>1
so c sub 2 = c sub (floor 2/2) + 2² = 0+4 = 4
and c sub 3 = c sub (floor 3/2) + 3² = 0+9 = 9
and c sub 4 = c sub (floor 4/2) + 4² = 4+16 = 20
and c sub 5 = c sub (floor 5/2) + 5² = 4+25 = 29
and c sub 6 = c sub (floor 6/2) + 6² = 9+36 = 45
I am attempting to prove c sub n < 4n² for all n≥1
So...basis step:
c sub 1 = 0
4(1)² = 4
0<4, hence, true
So we assume:
c sub k < 4k²
so
4k²>c sub (floor k/2) + k², which simplifies to
3k²>c sub (floor k/2)
Now for even k values, (floor k/2) = (floor [k+1]/2)
for odd k values, (floor [k+1]/2) = (floor k/2) + 1
So let's do k+1 for even k
4(k+1)²> c sub (floor [k+1]/2) + (k+1)², so
3(k+1)²> c sub (floor [k+1]/2)
As stated above (floor k/2) = (floor [k+1]/2), and 3k²>c sub (floor k/2)
3(k+1)² > 3k² true for all k≥1
Let's do an odd k
4(k+1)²> c sub (floor [k+1]/2) + (k+1)², so
3(k+1)²> c sub (floor [k+1]/2)
(floor [k+1]/2) = (floor k/2) + 1, so adding 1 to the left side of 3k²>c sub (floor k/2) yields 3k² + 1 > c sub (floor k/2) + 1
3(k+1)² > 3k² + 1 true for all k≥1
So it can be proven in both cases...but there has to be a more straightforward way of doing this...any ideas?
Thanks!
Neal
Turned off smilies - Ricky
Last edited by Ricky (2008-09-23 23:33:23)
Offline
First of all, no, I don't think there's an easier way of doing that problem. It doesn't really add much work to the problem, you just have to go through the same basic procedure twice.
Secondly, your proof is flawed. The proof of the odd n should look like this:
Not this:
Last edited by TheDude (2008-09-24 02:23:27)
Wrap it in bacon
Offline
Thanks!
I actually realized during my study group today as I was writing it out that I missed that part...details.
So how would I go about proving it for an odd case?
I'll chip away at it when I have a chance but any input is appreciated!
Neal
Offline
Don't simply assume that your hypothesis is correct just for k, make sure to point out that you assume that it is true for all n <= k. This means that it is valid to assume that
Now all you have to show is that
Wrap it in bacon
Offline
Pages: 1