# Another induction proof

1. Sep 30, 2006

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. Sep 30, 2006

### d_leet

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.

3. Sep 30, 2006

### bluevires

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
4. Sep 30, 2006

### d_leet

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.

5. Sep 30, 2006

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

$$a|b_{k+1}x_{k+1} = a | b_{k-1}x_{k-1} + b_{k}x_{k}$$ by Induction Hypothesis

Can i write $$a | b_{k-1}x_{k-1} + b_{k}x_{k}$$ as $$a | b_{k-1}x_{k-1} + a | b_{k}x_{k}$$ ? I doubt it? If yes then i know what to do next, otherwise i've no clue!

Last edited: Sep 30, 2006
6. Sep 30, 2006

### d_leet

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