I need help on these questions pleaseeee anyone, its on set thoery

  • Thread starter dhillon
  • Start date
  • #1
14
0

Main Question or Discussion Point

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
 

Answers and Replies

  • #2
14
0
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
 
  • #3
103
2
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.
 
  • #4
disregardthat
Science Advisor
1,854
33
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
does anyone know how you go about proving a set has cardinality, im not sure where to start, and im attemting the 2nd one one thanks once again
 
  • #7
disregardthat
Science Advisor
1,854
33
does anyone know how you go about proving a set has cardinality, im not sure where to start, and im 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.
 
  • #8
14
0
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
 
  • #9
14
0
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
disregardthat
Science Advisor
1,854
33
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
Redbelly98
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
12,100
129
This should probably be in the homework section..
Yes, it should. And the forum rules regarding homework help should apply as well.
 
Last edited:

Related Threads on I need help on these questions pleaseeee anyone, its on set thoery

Replies
0
Views
2K
  • Last Post
Replies
3
Views
2K
Replies
2
Views
2K
Replies
7
Views
5K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
Replies
4
Views
2K
Replies
1
Views
9K
Replies
57
Views
4K
Top