I on these questions pleaseeee anyone, its on set thoery

  • Thread starter Thread starter dhillon
  • Start date Start date
  • Tags Tags
    Set
AI Thread Summary
The discussion revolves around proving mathematical statements using induction, specifically focusing on two problems: proving that if n is odd, then n^2 - 1 is divisible by 8, and demonstrating that F3n is even for all n in the Fibonacci sequence. The proof for the first problem involves establishing a base case and showing that if the statement holds for an odd n, it also holds for n+2. Participants also discuss the concept of cardinality, particularly proving that certain sets have cardinality aleph-nought. The conversation highlights the need for clarity in questions and adherence to forum rules regarding homework assistance.
dhillon
Messages
14
Reaction score
0
n = any integer. prove that if n is odd then n^2 - 1 is divisble by 8

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

thanks for your help guys
 
Physics news on Phys.org
also does anyone know the 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??

thanks again
 
The proof to both of these relies on INDUCTION.

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.
 
Knowing some elementary number theory, you could check n^2-1 for the odd residues modulo 8.
 
thank you soooo much ...i'm reading through the working out now
 
does anyone know how you go about proving a set has cardinality, I am not sure where to start, and I am attemting the 2nd one one thanks once again
 
dhillon said:
does anyone know how you go about proving a set has cardinality, I am not sure where to start, and I am attemting the 2nd one one thanks once again

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 relation between sets. You can say that "the cardinality of A is larger than the cardinality of B" without defining "cardinality for A". In other words, |A|>|B| makes sense, but |A| does not. But you can also define the cardinality of a set as the smallest ordinal with the same cardinality. In this way each set "has" a cardinality. This definition is an extension of the previous, plus that now |A| makes sense.
 
the question is:

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
 
also could you help me with this ..i'm trying it and have spent the whole day reading about it but its not that clear to me ..thank you

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
dhillon said:
the question is:

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
Jarle said:
This should probably be in the homework section..
Yes, it should. And the forum rules regarding homework help should apply as well.
 
Last edited:
Back
Top