Results 1 to 6 of 6

Math Help - discrete math proofs

  1. #1
    Newbie
    Joined
    Dec 2005
    Posts
    3

    discrete math proofs

    1.) If n is the element of natural numbers and n is a perfect square, then the units digit of n is not 2.

    2.) If a,b is in the emement of natural numbers and both a and b are odd, then x^2+ax+b can not be factored into a product of two linear factors (a linear factor has the form cx+d, where c,d are elements of natural numbers)

    3.) Prove by Induction
    1+x+x^2+...+x^n=(x^(n+1)-1)/(x-1)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by innuenn
    1.) If n is the element of natural numbers and n is a perfect square, then the units digit of n is not 2.
    If n is a perfect square there is a natural number k such that n=k^2. Now write:

    k=t.10+u,

    where 0 \leq u \leq 9 is the units digit of k then

    k^2=100.t^2+20.t.u+u^2.

    So the units digit of n is equal to the units digit of u^2.

    Now look at the units digit of u^2 for u=0,1,\  ..\ 9 and you
    will see if this ever is equal to 2.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by innuenn
    2.) If a,b is in the emement of natural numbers and both a and b are odd, then x^2+ax+b can not be factored into a product of two
    linear factors (a linear factor has the form cx+d, where c,d are elements of natural numbers)
    Suppose that x^2+a.x+b with a and b
    odd, can be factored into a product of two
    linear factors c.x+d and e.x+f with
    c,\ d,\ e,\ f all natural numbers. Then:

    x^2+a.x+b = (c.x+d)(e.x+f)
    =c.e.x^2+(d.e+c.f).x+d.f
    .

    Now equate coefficients of corresponding powers of x:

    c.e=1

    d.e+c.f=a

    d.f=b

    As c and e are natural numbers
    the first of these equations implies c=e=1.
    Substituting these into the second equation gives:

    d+f=a

    Now the third of these equations implies both d and
    f are odd as by assumption b is odd.
    But d and f odd implies that their sum is
    even, but by assumption a is odd and is equal to the sum
    of d and f which is even - a contradiction.

    Hence x^2+a.x+b with a and b
    odd natural numbres, cannot be factored into a product
    of two such linear factors.

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2005
    Posts
    3
    thanks for the help
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    The answer to the last one, you can look up for a
    finite geometric series.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by innuenn
    3.) Prove by Induction
    1+x+x^2+...+x^n=(x^(n+1)-1)/(x-1)
    All inductive proofs have the same format.

    We have a proposition P(n) which we wish to prove true
    for all natural numbers or positive integers(or in more complicated cases
    something that can be reduced to this, but we are not in complicated cases
    country here )

    First we prove that the base case is true, in this problem that is that P(1)
    is true.

    Then we prove that if P(k) is true then P(k+1) is true.

    Finaly we can conclude from these that P(n) is true for
    all integers n \geq 1 by the principle of mathematical induction.

    ===============================================

    In this case P(n) is the proposition:

    For all real numbers x, and positive integer n

    1+x+x^2+...+x^n=\frac{x^{n+1}-1}{x-1}.

    The first step is to verify that P(n) is true when n=1
    (check that this holds in our case now).

    The next step is to show that if P(k) is true then P(k+1) is true.

    That P(k) is true means that for all real x that:

    1+x+x^2+...+x^k=\frac{x^{k+1}-1}{x-1}.

    If we add x^{k+1} to both sides to get:

    1+x+x^2+...+x^k+x^{k+1}=\frac{x^{k+1}-1}{x-1}+x^{k+1}.

    The LHS of this equation is the required LHS in P(k+1):

    1+x+x^2+...+x^k+x^{k+1}.

    So to show that P(k+1) is true we need to show that the RHS
    are equal, that is that:

    \frac{x^{k+1}-1}{x-1}+x^{k+1}=\frac{x^{k+2}-1}{x-1}.

    which I will leave for you to do.

    Then as we have shown P(1) is true and that whenever P(k) is true
    that P(k+1), we may conclude by mathematical induction that
    P(n) is true for all integers n \geq 1.

    Note: there are more direct methods of proving this result, but here
    you are asked to prove it by induction, so that is what we do

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: February 21st 2011, 10:12 AM
  2. I need help with these 7 discrete math proofs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 15th 2010, 02:11 AM
  3. Discrete Mathematics Problem (Proofs)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 10th 2009, 06:52 AM
  4. Discrete Math Proofs -- Need Help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 28th 2009, 02:24 AM
  5. little discrete math help
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 27th 2008, 08:47 AM

Search Tags


/mathhelpforum @mathhelpforum