Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

## #1 2005-10-31 05:55:17

barrence
Guest

### Mathematical Induction Conundrum

First Conundrum:

If possible, describe an induction principle for the set of
{0,−1,−2, . . .}. If this is not possible, give a brief explanation of why
it is not possible.

Second Conundrum:

Determine if there is a problem with the following proof by
induction that ‘all Canadians live inWaterloo.’ Give a brief explanation
of the problem.
Base case: consider the group of 0 Canadians; clearly all the Canadians
in the group live in Waterloo.

I.H. For any group of 0 <= k Canadians, all those k Canadians live in
Waterloo.
Consider a group of k + 1 Canadians. Remove Canadian c from the
group. The group consists of k Canadians, by the I.H. all those k
Canadians live in Waterloo. Pick one of the k Canadians, say d, d
lives in Waterloo. Remove d from the group and replace d with c. The
group still has k Canadians so, by the I.H., they all live in Waterloo.
Therefore all the k + 1 Canadians live in Waterloo.

## #2 2005-10-31 09:51:29

kylekatarn
Power Member

Offline

### Re: Mathematical Induction Conundrum

"consider the group of 0 Canadians; clearly all the Canadians
in the group live in Waterloo"
If there aren't canadians, how can you state something about them?

What's the mathematical or logical reasoning in "0 canadians clearly live in waterloo"?

## #3 2005-10-31 09:59:01

kylekatarn
Power Member

Offline

### Re: Mathematical Induction Conundrum

About the 1st "conundrum" (whatever that means...

Let S = Z\N U {0} and p(x) a statement where x ∈ S.
If you want to proof that p(x) is valid for all x ∈ S you:
1) proof that p(0) is true
2) proof that p(x-1) is also true for all x

## #4 2005-11-01 18:28:30

barrence
Guest

### Re: Mathematical Induction Conundrum

I'm not too sure I understand your notation for the solution to the first problem, could you restate that?

thanks for your patience

## #5 2005-11-01 20:48:13

kylekatarn
Power Member

Offline

### Re: Mathematical Induction Conundrum

Let S = {0,-1,-2,-3,...} and p(x) a statement (e.g.: "x+1>x for all x<-6" ; "2-x^2<x"; etc..).
x is a variable that can take values from our set S, only.

(Now the method is a kind of "backwards induction principle")
1) proof that p(0) is true - 0 is the 1st element of S
2) proof that p(x-1) is also true for all x, (x ∈ S).

If this is true, P(x) is valid for 0 and 0-1 = -1
Therefore is valid for -1 and -1-1 = -2...and so on. -3 -4 -5 -6 ....
So our statement is valid for all x ∈ S.

I don't know if this is an accepted induction method in today's math, but it seems correct to me since Z contains N and the symmetrics of N. N is an Inductive Set so i think -N (-1,-2,-3....) should also be inductive "backwards")