Creating Words of Length K from {1,...,k}: A Recursive Approach

[MathematicalPhysicist]

how many words of length k can you create from {1,...,k} such that 1 appears even number of times?
well, for k=0 we have 1, for k=1 we have zero, and for k=2 we have one.
i thought to use here a recursion formula.
but not quite sure how to do so, i mean if k>=3, and a_k stands for the number of legitiamte words, then if no 1 appears in the word then we have (k-1)^k words, let's assume that in a_k-1 1 appears even number times then for the the last number we have (k-1) choices, so i think that the equation should be:
a_k=(k-1)*a_k-1+(k-1)^k
am i correct here?
now if this is correct then how find a suitable private answer for non homogenoues part?

 

[MathematicalPhysicist]

my mistake for a_2 we have two options 22 and 11.

 

[matt grime]

You have written that the way to make a word of length k with an even number of 1s in it is to append a non-1 to a string of length k-1 with an even number of 1s. This is not true. Plus, you have over counted - why treat the string with no 1s in it separately and therefore counted it twice?

 

[MathematicalPhysicist]

so how would you go to solve this?
i saw a solution with power series, but didn't understand it.

 

[matt grime]

You should try to learn how to use power series (generating functions) - they are incredibly powerful.

If you really want a recurrence relation, then do the naive thing.

A string of length k is gotten by adding a digit to a string of length k-1. In order for this string of length k to have an even number of 1s, then the shorter string must have an even number of 1s and you append a non-1, or it has an odd number of 1s and you append a 1. So count them. Hint: do you need to count the number of strings with an odd number of 1s in or is there a way to write that in terms of strings with an even number of 1s?

 

[MathematicalPhysicist]

yes i know how to use power series, my problem is that i don't undersatnd the answer.
I'm given that for
$$F(x)=\sum_{n>=0} a_n*x^n=(1+x^2/2!+x^4/4!+...)(1+x+x^2/2!+...)^{(k-1)}$$ where a_n is the sequence we searching for.
but i don't understand how did they got to this, can you explain?


p.s
iv'e learned already generating functions, but still i don't see how arrive to this equation.