The valid codeword digits 0, 1, . . . , 7, the number of 0s must be odd. Determine how many such code-words of the length n-digits exist. Suppose, the code-words of a code can contain
only digits (0, 1, 2. 3. 4. 5,6, 7) while for a code-word, to be a valid code-word, the number of 0s must be odd.
1)how many such code-words of the length n-digits exist.
2)how to Set up the recurrence relation giving the number of code-words an of the length n and find the
3)how-to solution of this recurrence relation?
My solution:
codeword digits =( 0,1,2,3,4,5,6,7) and 0 odd number.So, a1=7.ending with non-zero= 7an−1.So, an=7an-1+8^n-1 -an-2.then an=6an-1+8^n-1 (actually i solve this like that but I have doubt about my selfe.maybe it's not perfectly correct.and I don't understand how to decorate this.) please some one help me I want to learn to solve like those type of problem solve solution
 A: Deriving a recurrence relation
To make a recurrence relation for $a_n$, let's break into cases based on whether the last digit is 0.
How many possibilities exist where the last digit is 0? Well, we just need any codeword of length $n-1$ with an even number of 0s, so that we'll get an odd number of 0s after we include the extra 0 on the end. The total number of codewords of length $n-1$ is $8^{n-1}$, and $a_{n-1}$ of those have an odd number of zeros, so $8^{n-1} - a_{n-1}$ is the number with an even number of zeros.
How many possibilities exist where the last digit is not 0? Well, the last digit could be anything from 1-7 (7 options) and the first $n-1$ digits could be any codeword of length $n-1$ with an odd number of 0s ($a_{n-1}$ options), so we have $7 a_{n-1}$ options in total.
Combining those two cases, we find $a_n = 8^{n-1} - a_{n-1} + 7 a_{n-1}$, or $a_n = 6 a_{n-1} + 8^{n-1}$. We can also quickly check the base case $a_1 = 1$.
Solving the recurrence relation
There are some fancy tricks that let you solve lots of recurrence relations, but those are also more complicated to learn. I'd start out with a simpler strategy: Just plug into the recurrence relation repeatedly and try to find a pattern. In this case, we see:
$$
\begin{align}
a_n &= 8^{n-1} + 6 a_{n-1} \\
&= 8^{n-1} + 6(8^{n-2} + 6 a_{n-2}) \\
&= 8^{n-1} + 6 \cdot 8^{n-2} + 6^2 a_{n-2} \\
&= 8^{n-1} + 6 \cdot 8^{n-2} + 6^2 (8^{n-3} + 6 a_{n-3}) \\
&= 8^{n-1} + 6 \cdot 8^{n-2} + 6^2 \cdot 8^{n-3} + 6^3 a_{n-3} \\
&\quad \vdots \\
&= 8^{n-1} + 6 \cdot 8^{n-2} + 6^2 8^{n-3} + 6^3 8^{n-4} + \cdots + 6^{n-2} 8^1 + 6^{n-1} a_1 \\
&= 8^{n-1} \left( 1 + \frac{6}{8} + \left(\frac 6 8\right)^2 + \cdots \left( \frac 6 8 \right)^{n-1}\right) \\
&= 8^{n-1} \left( \frac{1 - \left(\frac 6 8 \right)^n} {1-\frac 6 8} \right) \\
&= 8^{n-1} \cdot 4\left(1 - \left(\frac 3 4 \right)^{n}\right) \\
&= 2^{3n-1} - 2^{n-1} 3^n
\end{align}
$$
So the final formula is $a_n = 2^{3n-1} - 2^{n-1} 3^n$.
Pointer for further reading
If you want to read about general methods for solving such recurrence relations, instead of just rolling up your sleeves and simplifying everything by hand like I did above, then you should look up "Solving non-homogeneous linear recurrence relations". There are a couple of different methods (that mostly work for the same reasons behind the scenes). I don't have one particular link to recommend but you can find a lot of articles, course slides, YouTube tutorials, etc. if you get interested and want to Google it.
