Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Another induction proof

  1. Sep 30, 2006 #1
    hey guys

    I'm stuck with another induction proof.

    Question: Suppose a, b1, b2,...,bn are integers with a|b1 (means a divides b), a|b2, ..., a|bn. Prove by induction on n that a|b1x1 + b2x2 + ... + bnxn for all integers x1, x2,..., xn.

    This is what i've, please let me know if it's correct. The question basically have connection of Proposition division alogrithm.
    Base case:
    Show that result is true for n = 1;
    Since it's already given that when n = 1 then a|b1
    therefore we can write b1 = aq for some inetger q. So b1x1 = aq(x1) = a(qx1) where q and x1 are integers. Hence a|bx1. Therefore, result holds for n = 1

    Induction hypothesis: Assume reuslt holds for n = k.

    I'm not too sure what to do next? Please someone help me with this, thanks in advance!
  2. jcsd
  3. Sep 30, 2006 #2
    You need to use the form of induction where you make the assuption that what you are trying to prove is true for all integers 1,2,3...k.
  4. Sep 30, 2006 #3
    after you let n=k
    you need to prove the case also holds true for n = k+1

    in order to do this, u'll probably need to write out the case in the sequence form, then subsitute part of the equation into n=k, then do some algebra work from that point to get to the answer for n = k+1

    sorry I'm not really clear about the question you are asking, it might help if you use LaTex equations.
    Last edited: Sep 30, 2006
  5. Sep 30, 2006 #4
    You don't "let n=k" you assume the statement is true for n=k, but this problem won;t work using that form of induction as I pointed out above.

    Can you tell me how you would put the statement he is trying to prove true into sequence form? Also I'm not sure exactly what you mean by sequence form.

    I think his post was clear enough that it was fairly easy to determine what he was trying to prove.
  6. Sep 30, 2006 #5
    I thought of that too, it's called strong induction but i'm not too sure if what i did make sense. This is what i have

    Induction Hypothesis: Assume reuslt holds for n = 1, 2,... ,k for some intger k, k >= 1.

    Innduction Conclusion: Conisder n = k + 1

    [tex]a|b_{k+1}x_{k+1} = a | b_{k-1}x_{k-1} + b_{k}x_{k} [/tex] by Induction Hypothesis

    Can i write [tex]a | b_{k-1}x_{k-1} + b_{k}x_{k}[/tex] as [tex]a | b_{k-1}x_{k-1} + a | b_{k}x_{k}[/tex] ? I doubt it? If yes then i know what to do next, otherwise i've no clue!
    Last edited: Sep 30, 2006
  7. Sep 30, 2006 #6
    No I don't think that you can do that but you do know that a divides bn for all integers n, if you use this fact and try the case for n=2 or n=3 I think you might be able to see better how to prove this.

    EDIT: Also note that you are trying to prove a|b1x1 + b2x2 + ... + bnxn and that bk+1xk+1 is not equal to bkxk+bk-1xk-1
    Last edited: Sep 30, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook