How Do You Prove That a Divides a Linear Combination in Induction?

[salubadsha]

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!

 

[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.

 

[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.

 

[d_leet]

after you let n=k

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.

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 forum, 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

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.

sorry I'm not really clear about the question you are asking, it might help if you use LaTex equations.

I think his post was clear enough that it was fairly easy to determine what he was trying to prove.

 

[salubadsha]

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.

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!

 

[d_leet]

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}$$

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!

No I don't think that you can do that but you do know that a divides b_n 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|b₁x₁ + b₂x₂ + ... + b_nx_n and that b_k+1x_k+1 is not equal to b_kx_k+b_k-1x_k-1