- #1

- 14

- 0

i was thinking of finding a contrapositive, not sure what to do

thanks for your help guys

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter dhillon
- Start date

- #1

- 14

- 0

i was thinking of finding a contrapositive, not sure what to do

thanks for your help guys

- #2

- 14

- 0

thanks again

- #3

- 103

- 2

The basic idea behind induction is the following:

1) Prove that a statement P(n) is true for n=1.

2) Prove that if P(n) is true, then P(n+1) is true, so long as n is at least 1.

If we can prove the above two statements, then we have proven P(n) is true for any n that is at least 1. This is because P(1) is true, so P(2) is true, so P(3) is true, so P(4) is true... and so on.

Now, here's how we prove your first problem:

"P(n)" means "n^2 - 1 is divisible by 8".

P(1) is obviously true, as n^2 - 1 = 0, which is divisible by 8.

Now, suppose for some odd n, P(n) is true. (i.e., n^2 - 1 is divisible by 8). We want to prove that this implies that P(n+2) is true.

"P(n+2)" means "(n+2)^2 - 1 is divisible by 8", which means "n^2 + 4n + 4 - 1 is divisible by 8" which means "(n^2 - 1) + (4n + 4) is divisible by 8".

But this is also clearly true! We know n^2 - 1 is divisible by 8 by assumption. We also know that 4n + 4 is divisible by 8 for any odd n. Thus the whole thing is divisible by 8.

By induction we are done.

Now, you try the second problem.

- #4

disregardthat

Science Advisor

- 1,861

- 34

Knowing some elementary number theory, you could check n^2-1 for the odd residues modulo 8.

- #5

- 14

- 0

thank you soooo much ....i'm reading through the working out now

- #6

- 14

- 0

- #7

disregardthat

Science Advisor

- 1,861

- 34

Can you explain your question a bit better? The notion of cardinality is not restricted to sets with a "given" cardinality, it can be treated as a

- #8

- 14

- 0

Prove that these sets have cardinality aleph-nought:(there is two 2 prove)

(a) {1/(2^k) : k∈ℕ}

(b) {x∈ℤ : x >= -5}

once again thank you, i hope the question makes sense more

- #9

- 14

- 0

fibonacci sequence which is defined by F1=1, F2=2, Fn= Fn-1 + Fn-2 for all n>=3 . anyone know how to prove F3n is even for all n?

- #10

disregardthat

Science Advisor

- 1,861

- 34

Prove that these sets have cardinality aleph-nought:(there is two 2 prove)

(a) {1/(2^k) : k∈ℕ}

(b) {x∈ℤ : x >= -5}

once again thank you, i hope the question makes sense more

This should probably be in the homework section..

Last edited by a moderator:

- #11

- 12,121

- 160

Yes, it should. And the forum rules regarding homework help should apply as well.This should probably be in the homework section..

Last edited:

Share: