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

You are not logged in.

## #1 2005-10-30 06: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-30 10:51:29

kylekatarn
Member
Registered: 2005-07-24
Posts: 445

### Re: Mathematical Induction Conundrum

in the group live in Waterloo"

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

Offline

## #3 2005-10-30 10:59:01

kylekatarn
Member
Registered: 2005-07-24
Posts: 445

### 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

Offline

## #4 2005-10-31 19: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?

## #5 2005-10-31 21:48:13

kylekatarn
Member
Registered: 2005-07-24
Posts: 445

### 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")

Offline