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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**barrence****Guest**

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.

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

"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"?

Offline

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

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

**barrence****Guest**

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

thanks for your patience

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

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

Pages: **1**