Mathematical Induction - Introductory Question

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

MathDoofus
Posts: 247
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Wed May 03, 2017 4:39 pm UTC

Demki wrote:
MathDoofus wrote:
Meteoric wrote:Yes! That is a valid argument, and a perfect example of proof by induction. You have the base step, the induction step, and you correctly justify your conclusion using known properties of even and odd numbers.


But my argument still contains an assumption that I'd need to build out (I think), which is that every positive integer is either cleanly divisible by two or not. I'm not sure how I'd deal with in a proof by induction.

So instead of using the definitions:
"Even" - a number cleanly divisible by 2
"Odd" - a number not divisible by 2
Use the definitions:
"Even" - a number cleanly divisible by 2
"Odd" - a number one greater than a number cleanly divisible by 2

This way you are tasked to prove that every integer that isn't even is odd.
The steps are basically the same as what you said earlier, just with a bit more justification as to why "an odd number + 1 is even"

I mean, clearly if we replace the 2s in these definitions with a 3, then the first set of definition still cover every integer, yet the second set doesn't (every integer of the form 3n+2 is missing)

And this is why it is important to state your definitions clearly.


Gotcha - thinking through this, however, I guess I haven't accounted for the case of 1, which is odd (I think) but doesn't get swept into the definition of "a number greater than a number cleanly divisible by 2," unless we count 0 as a number (but it's not a positive integer).

Demki
Posts: 182
Joined: Fri Nov 30, 2012 9:29 pm UTC

Re: Mathematical Induction - Introductory Question

Postby Demki » Wed May 03, 2017 4:42 pm UTC

The even/odd definition I posted apply for all integers, not just the positive ones. 0 is a multiple of 2(2*0=0), therefore it is even. 0 is divisible by every number except 0.

Meteoric
Posts: 332
Joined: Wed Nov 23, 2011 4:43 am UTC

Re: Mathematical Induction - Introductory Question

Postby Meteoric » Wed May 03, 2017 4:45 pm UTC

Right, exactly. You're correct that if we take "odd" to mean "not even", then there's nothing to prove. But under the standard definition about 2m and 2m+1, it takes a little bit of justification.

Clearly, if I take 2m and add 1, then I've got 2m+1 which is odd. But what if I take 2m+1 and add 1? Then I've got 2m+2. Can I write that as "2 times some whole number"? That would show that an odd number plus 1 makes an even number.
No, even in theory, you cannot build a rocket more massive than the visible universe.

MathDoofus
Posts: 247
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Wed May 03, 2017 5:11 pm UTC

Meteoric wrote:Right, exactly. You're correct that if we take "odd" to mean "not even", then there's nothing to prove. But under the standard definition about 2m and 2m+1, it takes a little bit of justification.

Clearly, if I take 2m and add 1, then I've got 2m+1 which is odd. But what if I take 2m+1 and add 1? Then I've got 2m+2. Can I write that as "2 times some whole number"? That would show that an odd number plus 1 makes an even number.


That makes sense. I'm going to study the chart that shows how the even-odd problem fits into the induction rubric.

MathDoofus
Posts: 247
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Sat May 06, 2017 9:45 pm UTC

I've spent some time thinking about induction, and I've figured out that I don't have the algebra skills to complete any induction problem right now. I simply don't know the re-writing rules well enough to perform the symbol-magic to get at a solution. Nevertheless, can someone tell me why the proof below is different from what we've been doing in this thread?

Let's assume that S(n)=n*(n+1)/2
S(n+1)=Sum of first (n+1) terms
= Sum of first 'n' terms + (n+1)th term
= n*(n+1)/2 + (n+1)
= (n^2+n+2*n+2)/2
= (n^2+3*n+2)/2
= (n+1)*(n+2)/2
= ( (n+1) )* ( (n+1) + 1 ) / 2

Demki
Posts: 182
Joined: Fri Nov 30, 2012 9:29 pm UTC

Re: Mathematical Induction - Introductory Question

Postby Demki » Sat May 06, 2017 10:04 pm UTC

It's not, it is just missing a base case.

MathDoofus
Posts: 247
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Sat May 06, 2017 10:05 pm UTC

Demki wrote:It's not, it is just written differently, and is missing a base case.


OK. I have some vague notion that, in solving the original question, I don't want the left-hand side to look the same as the right-hand side. Instead, I want to manipulate the right-hand side to look like something else. Is that right?

Demki
Posts: 182
Joined: Fri Nov 30, 2012 9:29 pm UTC

Re: Mathematical Induction - Introductory Question

Postby Demki » Sat May 06, 2017 10:11 pm UTC

Yes, basically. What you want is simply to derive the (n=k+1) case given the (n=k) case, as has been done in the proof you've given, along with a base case.

MathDoofus
Posts: 247
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Sat May 06, 2017 10:23 pm UTC

Demki wrote:Yes, basically. What you want is simply to derive the (n=k+1) case given the (n=k) case, as has been done in the proof you've given, along with a base case.


Gotcha. How do I know when I've correctly derived the k + 1 case (the then) from the k case (the if)?

User avatar
Flumble
Yes Man
Posts: 1779
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Mathematical Induction - Introductory Question

Postby Flumble » Sun May 07, 2017 2:52 am UTC

MathDoofus wrote:
Demki wrote:Yes, basically. What you want is simply to derive the (n=k+1) case given the (n=k) case, as has been done in the proof you've given, along with a base case.


Gotcha. How do I know when I've correctly derived the k + 1 case (the then) from the k case (the if)?

You start with the statement with a k in the place of the relevant variable (usually n), then, through applying a series of mathematically valid transformations (like algebra or logic), you end up with the statement with k+1 in the place of the variable. (I tried to convey this in the diagrams too)
Your derivation is correct if the transformations are correct.

User avatar
ucim
Posts: 5091
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Mathematical Induction - Introductory Question

Postby ucim » Sun May 07, 2017 4:17 am UTC

MathDoofus wrote:Gotcha. How do I know when I've correctly derived the k + 1 case (the then) from the k case (the if)?


Start with
left_side(k) = right_side(k)
You know this is true for at least one k. (That was your first step.)

Now write
left_side(k+1) =? right_side(k+1)
You don't know this is true yet. The object is to get this to look like what you started with. Bit by bit you get the left side to look like it's earlier form, while doing exactly the same thing to the right side (to maintain the supposed equality). When simplified, the right side should comply also, and you'll be there.

If you do correct algebra, and you mange to get your first equation back, you've done it.

Hint: The second-to-last stage will probably look something like
left_side(k) + 1 =? right_side(k) + 1
and subtracting 1 from both sides gets you home. What it actually looks like depends on the equations involved.

Then, you can replace the =? in that last step with = (because you know the last step is true).... and working backwards you know the previous steps must have also been true. You end up replacing =? with = in the beginning, and add a Latin TLA at the end.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

User avatar
Eebster the Great
Posts: 2475
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Mathematical Induction - Introductory Question

Postby Eebster the Great » Sun May 07, 2017 5:14 am UTC

If you find function notation to be beyond your grasp, it's a good bet you don't really understand how substitution actually works, which seems to be evident from your posts in this thread. In that case, you are naturally going to have a tough time understanding what "the k+1 case" even means.

MathDoofus
Posts: 247
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Sun May 07, 2017 12:53 pm UTC

Eebster the Great wrote:If you find function notation to be beyond your grasp, it's a good bet you don't really understand how substitution actually works, which seems to be evident from your posts in this thread. In that case, you are naturally going to have a tough time understanding what "the k+1 case" even means.


Thanks. Always helps to have someone pile on to point out my ignorance, which I've confessed many times in this thread. The point of this thread is so that I can work out each step. Thank you to those who've tried to help with that.


Return to “Mathematics”

Who is online

Users browsing this forum: Baidu [Spider], Bing [Bot] and 2 guests