Results 1 to 6 of 6

Math Help - cardinality and divisibility

  1. #1
    Junior Member
    Joined
    Aug 2006
    Posts
    34

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    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).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1
    Quote Originally Posted by action259 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1
    Quote Originally Posted by topsquark View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by action259 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by action259 View Post

    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)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 8th 2009, 03:23 PM
  2. cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 3rd 2008, 08:26 AM
  3. cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 19th 2008, 09:03 AM
  4. cardinality
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2008, 08:18 PM
  5. cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 9th 2008, 04:37 AM

Search Tags


/mathhelpforum @mathhelpforum