Let $A_n$ be the set of all finite words over the alphabet $\{1,2,3\}$ whose digits sum to $n$. I am trying to find a recurrence relation with initial conditions for $|A_n|$. I have checked the first few $n$ and got that $|A_1|=1$ , $|A_2|=2$, $|A_3|=4$, $|A_4|=7$, $|A_5|=13$, $|A_6|=24$. I can't seem to find a pattern that allows me to create a recurrence relation, nor I am I sure how I could check that such a pattern would be correct.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.