Prove the following: an−bn=(a−b)n−1∑k=0akbn−1−k.
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 an−bn 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 a−b choices for this letter, ak choices for the letters before this letter, and bn−k−1 choices for the letters after this letter. Thus there are (a−b)akbn−k−1 such words, and summing over all k gives
an−bn=(a−b)n−1∑k=0akbn−k−1
as desired.
No comments:
Post a Comment