Saturday, 5 May 2018

algebra precalculus - Algebraic Identity anbn=(ab)sumlimitsn1k=0akbn1k



Prove the following: anbn=(ab)n1k=0akbn1k.



So one could use induction on n? Could one also use trichotomy or some type of combinatorial argument?


Answer



I have no idea what you mean by "use trichotomy," but here is the combinatorial argument. an counts the number of words of length n on the alphabet {1,2,...a} and bn counts the number of words of length n on the alphabet {1,2,...b}. Assume a>b. Then anbn counts the number of words of length n on the alphabet {1,2,...a} such that at least one letter is greater than b.




Given such a word, suppose the last letter greater than b occurs at position k+1. Then there are ab choices for this letter, ak choices for the letters before this letter, and bnk1 choices for the letters after this letter. Thus there are (ab)akbnk1 such words, and summing over all k gives



anbn=(ab)n1k=0akbnk1




as desired.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...