Saturday, November 14, 2015

discrete mathematics - prove by induction that (anbn) is a multiple of (ab) for ngeq1





Okay so I just finished a final in discrete mathematics and I could not figure out how to finish this proof:



"Prove by mathematical induction, that (anbn) is a multiple of (ab) when a and b are integers and n1.



Basecase:n=1_




(a1b1)=(ab)x



x=1



ab=ab



InductiveHypothesis:_



n=k for some k




(akbk)=(ab)x



InductiveStep:_



n=k+1



(ak+1bk+1)=(ab)x1



(aak)(bbk)=(ab)x1




a[(ab)x+bk]+b[(ab)xak]=(ab)x1



(ab)xa+abk+(ab)xbbak=(ab)x1



(ab)xa+(ab)xbabk+bak=(ab)x1



(ab)xa+(ab)xb+bakabk=(ab)x1



.....




I don't know if I did it right but I couldn't get any further than this.


Answer



Assumed akbk=(ab)m,mZak=bk+(ab)m



We have ak+1bk+1=a×akbk+1=a[bk+(ab)m]bk+1=am(ab)+abkbk+1=am(ab)+bk(ab)=(am+bk)(ab)


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...