Thread: cardinality and divisibility

I have 2 proofs i can't seem to get

one is prove by induction the power set

abs(P(A))=2^n where abs(A)=n

I think you need to use a binomial theorem of sorts to solve this one

another one that is giving me trouble is

3 divides n if and only if 3 divides the sum of the digits of n, where n is a positive integer

this one is also an induction proof thanks for any help

If A={1} then P(A)={o,{1}} where o is the empty set.
So |P(A)|=2^1. Now suppose A={1,2,3,…,k} and |P(A)|=2^k.
We must consider the set A’={1,2,3,…,k,k+1}.
Note that A’=AU{k+1}={1,2,3,…,k}U{k+1}.
That means if B is in P(A’) then B is in P(A) or B=CU{k+1} where C is in P(A).
Thus |P(A’)|=2^k+2^k=2^(k+1).
So if n is positive integer, then for {1,2,3,…,n} and |P({1,2,3,…,n})|=2^n.

A second way is to use the binomial theorem.
(x+y)^n = SUM_{k=0 to n} Combin(n,k)x^k y^(n-k).
The number of subsets of a set of n elements with exactly k elements is Combin(n,k).
Let x=1 & y=1 then we have (2)^n = SUM_{k=0 to n} Combin(n,k).

Originally Posted by action259

3 divides n if and only if 3 divides the sum of the digits of n, where n is a positive integer

this one is also an induction proof thanks for any help

Note that
10 = 1 (mod 3)
100 = 10*10 = 1*1 (mod 3) = 1 (mod 3)
etc.
so that
10^n = 1 (mod 3)

and
a*10^n = a*1 (mod 3) = a (mod 3)

Now, any number in base 10 can be written as
(Sum, i = 1 to n)a_i*10^i = (Sum, i = 1 to n)a_i*1 (mod 3) = (Sum, i = 1 to n) a_i (mod 3)
which is simply the sum of the digits of the number.

But (Sum, i = 1 to n) a_i is divisible by 3 if and only if (Sum, i = 1 to n) a_i = 0 (mod 3), thus the number (Sum, i = 1 to n) a_i*10^i is divisible by 3 iff (Sum, i = 1 to n) a_i is divisible by 3.

-Dan

Originally Posted by topsquark

Note that
10 = 1 (mod 3)
100 = 10*10 = 1*1 (mod 3) = 1 (mod 3)
etc.
so that
10^n = 1 (mod 3)

and
a*10^n = a*1 (mod 3) = a (mod 3)

Now, any number in base 10 can be written as
(Sum, i = 1 to n)a_i*10^i = (Sum, i = 1 to n)a_i*1 (mod 3) = (Sum, i = 1 to n) a_i (mod 3)
which is simply the sum of the digits of the number.

But (Sum, i = 1 to n) a_i is divisible by 3 if and only if (Sum, i = 1 to n) a_i = 0 (mod 3), thus the number (Sum, i = 1 to n) a_i*10^i is divisible by 3 iff (Sum, i = 1 to n) a_i is divisible by 3.

-Dan

Given the lack of LaTeX it occurs to me that you might want an example of this.

So take the number 9812.

9812 = 9*10^3 + 8*10^2 + 1*10^1 + 2*10^0
Individually the terms:
9*10^3 = 9*1 (mod 3) = 9 (mod 3) = 0 (mod 3)
8*10^2 = 8*1 (mod 3) = 8 (mod 3) = 2 (mod 3)
1*10^1 = 1*1 (mod 3) = 1 (mod 3) = 1 (mod 3)
2*10^0 = 2*1 (mod 3) = 2 (mod 3) = 2 (mod 3)

So the number
9812 = 9 + 8 + 1 + 2 (mod 3) = 0 + 2 + 1 + 2 (mod 3) = 5 (mod 3) = 2 (mod 3)

Thus we know that 9812 is not divisible by 3.

-Dan

Originally Posted by action259

I have 2 proofs i can't seem to get

one is prove by induction the power set

abs(P(A))=2^n where abs(A)=n

I will assume that |A| is finite.
The number of ways to choose zero elements i.e. empty set
Is,
nC0
The number of ways to choose 1 elements sets is,
nC1
...
And so one.
Thus,
nC0+nC1+nC2+...+nCn=2^n

Because,
2^n=(1+1)^n
Apply binomial expansion.

Originally Posted by action259

3 divides n if and only if 3 divides the sum of the digits of n, where n is a positive integer

In number theory there is a nice theorem about congruences.
If,
a = b(mod n)
And if,
P(x) is a polynomial function in Z[x], i.e. integrers. Then,
P(a)=P(b)(mod n)
Now,
10=1(mod 3)
Thus,
P(10)=P(1) (mod 3)
Note that,
P(1)=SUM OF DIGITS
P(10)=NUMBER IN BASE TEN.
Thus,
NUMBER=SUM (mod 3)
Thus,
3| NUMBER if and only if 3|SUM.
----
You can extende this to 9.
Since,
10=1(mod 9)
We have,
P(10)=P(1) (mod 9)
Same idea as before.
---
In fact you can generalize this to other number bases.
If n is a number in base m.
Then,
(m-1)|n if and only if (m-1)|(SUM OF DIGITS)