One is allowed to use the digits 5,6,7,8 any number of times to form a terminate number. A n digit terminate number is one which contains digit 5 either an even number of times or does not contain digit 5 at all.
eg 556,55,876565 , 8 ,6 are all legitimate numbers
My attempt.
Considering an n digit number .
5 can occur 0,2,4,6... t times
Calculating this t with respect to n seems to be a problem. Moreover,if we know t, number of possibilities would be many
For instance 5 occurring 2 times could be generalised as
$nC2\times3^{n-2}$
However arranging the digits of the above number would itself more ways .
I was hoping to know another way to think of this problem and generalise it for a n digit terminate number.
answer given is
$2^{n-1}(2^n + 1)$
In the sequel we only look at numbers that have their digits in $\{5,6,7,8\}$
Let $t_n$ denote the number of terminate numbers of $n$ digits.
Let $s_n$ denote the number of non-terminate numbers $n$ digits.
Starting with a conventional $t_0=1$ and $s_0=0$ we can find these numbers recursively by means of the following equations:
$$\begin{aligned}t_{n+1}=3t_{n}+s_{n}\\ s_{n+1}=t_{n}+3s_{n} \end{aligned} $$ The $t_n$ terminate numbers of $n$ digits all provide $3$ terminate number of $n+1$ digits by adding digit $6,7$ or $8$. The $s_n$ non-terminate numbers of $n$ digits provide $1$ terminate number by adding digit $5$. This declares the first equality, and the second can be explained likewise.
Based on these equalities by induction it can be shown that:$$\begin{aligned}t_{n}=2^{n-1}\left(1+2^{n}\right)\\ s_{n}=2^{n-1}\left(2^{n}-1\right) \end{aligned} $$
I found the equalities myself but could not make anything of them. What helped was some searching on OEIS. Here and here.