Combinatorics: How many distinct binary strings of length 16 are possible if the zeroes must appear in groups of even number? I am trying to solve two combinatorics problems. May you help me?
First problem,
How many distinct binary strings of length 16 are possible if the zeroes must appear in groups of even number?
I think that the key is to see that there can be even number of zeroes or odd number of zeroes. The total number of possible lists is 2^16. Half of them has even number of zeroes. Thus the answer is 2^15.
Second problem,
What if the zeroes need to be in pairs? 
Then lists that start with 01 are not allowed. Also strings that have 101, or 10001, or 1000001, etc. are not allowed. I have been thinking that if the number of zeroes need to be in pairs... The number of ones need to be in pairs, as well!
Then we just need to use the same strategy. We divide the original 16 in squares of size 2. Then we have 8 squares. The total number of possible lists is 2^8. All are even, of course, because 0 is even too.
Is my reasoning correct? Thank you for everything!
 A: For the first problem using $w$ for the one digit and $z$ for the zero
digit we get from first principles the generating function
$$G(z, w) =
\left(1+w+w^2+w^3+\cdots\right) \\ \times
\left(\sum_{q\ge 0} (z^2+z^4+z^6+\cdots)^q (w+w^2+w^3+\cdots)^q\right)
\left(1+z^2+z^4+z^6+\cdots\right).$$
This simplifies to
$$G(z, w) = \frac{1}{1-w}
\left(\sum_{q\ge 0} \left(\frac{z^2}{1-z^2}\right)^q
\left(\frac{w}{1-w}\right)^q\right)
\frac{1}{1-z^2}
\\ = \frac{1}{1-w}
\frac{1}{1-wz^2/(1-w)/(1-z^2)}
\frac{1}{1-z^2}
\\ = \frac{1}{1-w-z^2+wz^2-wz^2}
= \frac{1}{1-w-z^2}.$$
Now as we are only interested in the count we may drop the distinction
between $w$ and $z$ to get
$$G(z) = \frac{1}{1-z-z^2}.$$
Extracting coeffcients we find for $n\ge 2$
$$[z^n] G(z) (1-z-z^2) = [z^n] 1 = 0$$
which gives the recurrence
$$g_n-g_{n-1}-g_{n-2} = 0$$
or $$g_n = g_{n-1} + g_{n-2}$$
so these are Fibonacci numbers. Since  $g_0 = 1$ (a zero length string
contains zero zeroes, an even number) and $g_1 = 1$ (the zero digit is
not admissible but the one digit is) our answer becomes
$$\bbox[5px,border:2px solid #00A000]{ F_{n+1}.}$$
Here  is  a  Maple  script  that can  be  adapted  easily  to  provide
enumeration data when runlength formulae are computed.

RL :=
proc(n)
option remember;
local ind, d, pos, cur, run, runs, res,
    allz, evenz;

    res := 0;

    for ind from 2^n to 2*2^n-1 do
        d := convert(ind, base, 2);

        cur := -1; pos := 1;
        run := []; runs := [];


        while pos <= n do
            if d[pos] <> cur then
                if nops(run) > 0 then
                    runs :=
                    [op(runs), [run[1], nops(run)]];
                fi;

                cur := d[pos];
                run := [cur];
            else
                run := [op(run), cur];
            fi;

            pos := pos + 1;
        od;

        runs := [op(runs), [run[1], nops(run)]];

        allz := select(r -> r[1] = 0, runs);
        evenz := select(r -> type(r[2], even), allz);

        if nops(allz) = nops(evenz) then
            res := res + 1;
        fi;
    od;

    res;
end;

A: In order to count the number of strings of length $16$  having even runs of $0$s resp. pairs of $0$s we consider words
with no consecutive equal characters at all.
These words are called Smirnov words or Carlitz words. (See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.) 
A generating function for the number of Smirnov words over a binary alphabet is given by
\begin{align*}
\left(1-\frac{2z}{1+z}\right)^{-1}\tag{1}
\end{align*}

First problem: Even runs of $0$s
We replace occurrences of $0$ in a Smirnov word by an even number of zeros.  This corresponds to a substitution of
  \begin{align*}
z&\longrightarrow z^2+z^4+z^6+\cdots=\frac{z^2}{1-z^2}\tag{2}\\
\end{align*}
   and we replace occurrences of $1$ in a Smirnov word by any run of $1$'s with length $\geq 1$.
  \begin{align*}
z&\longrightarrow z+z^2+z^3+\cdots=\frac{z}{1-z}\tag{3}\\
\end{align*}
We obtain by substituting (2) and (3) in (1) a generating function A(z)
  \begin{align*}
A(z)&=\left(1-\frac{\frac{z^2}{1-z^2}}{1+\frac{z^2}{1-z^2}}-\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}\right)^{-1}\\
&=\frac{1}{1-z-z^2}\\
&=1+z+2z^2+3z^3+5z^4+8z^5+13z^6\cdots+\color{blue}{1597}z^{16}+\cdots
\end{align*}

with $A(z)$ a generating function of the Fibonacci numbers.

Second problem: All runs of $0$ having length $2$
We can do a similar approach as above. Here we use the substitution
\begin{align*}
z&\longrightarrow z^2\tag{4}\\
z&\longrightarrow z+z^2+z^3+\cdots=\frac{z}{1-z}\tag{5}\\
\end{align*}
We obtain by substituting (4) and (5) in (1) a generating function B(z)
  \begin{align*}
B(z)&=\left(1-\frac{z^2}{1+z^2}-\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}\right)^{-1}\\
&=\frac{1+z^2}{1-z-z^3}\tag{6}\\
&=1+z+2z^2+3z^3+4z^4+6z^5+9z^6\cdots+\color{blue}{406}z^{16}+\cdots
\end{align*}

The series expansion of $A(z)$ and $B(z)$ was done with the help of Wolfram Alpha.

We can derive a recurrence relation from the generating function easily and we obtain from (6) (similarly as it is shown in @MarkoRiedel's answer)
  \begin{align*}
[z^n]B(z)(1-z-z^3)=[z^n](1+z^2)=0
\end{align*}
  and conclude
  \begin{align*}
g_n-g_{n-1}-g_{n-3}&=0\\
g_0&=g_1=1\\
g_2&=2
\end{align*}

Finally we look at an example and consider the number of valid words of length $6$.

We obtain nine solutions
  $$\begin{array}{cccccc}
1&1&1&1&1&1\\
\color{blue}{0}&\color{blue}{0}&1&1&1&1\\
1&\color{blue}{0}&\color{blue}{0}&1&1&1\\
1&1&\color{blue}{0}&\color{blue}{0}&1&1\\
1&1&1&\color{blue}{0}&\color{blue}{0}&1\\
1&1&1&1&\color{blue}{0}&\color{blue}{0}\\
\color{blue}{0}&\color{blue}{0}&1&\color{blue}{0}&\color{blue}{0}&1\\
\color{blue}{0}&\color{blue}{0}&1&1&\color{blue}{0}&\color{blue}{0}\\
1&\color{blue}{0}&\color{blue}{0}&1&\color{blue}{0}&\color{blue}{0}\\
\end{array}
$$
  in accordance with $[z^6]B(z)=9$.

A: If no $0$s appear then there is exactly one binary sequence. Assume that the sequence has exactly two zeros. Since they can only come in pairs then we can look at $00$ as one $0$ in a sequence of length $15$. There are ${15}\choose{1}$ sequences with two zeros coming in pairs. Same applies if there are $4$ zeros. Then there are ${14}\choose{2}$ sequences with zeros coming in even pairs. By proceeding we have 
$$1+\binom{15}{1}+\binom{14}{2}+\binom{13}{3}+\cdots +\binom{16-k}{k}+\cdots +\binom{9}{7}+1$$ binary sequences with $0$s appearing in even numbers. 
The second part is left as an exercise.
A: Problem $1$
As you have mentioned there are $2^{16}$ and since an odd number cant be partitioned into a sum of even number then we know an odd number of zeroes would mean that there will an odd grouping of zeroes so that narrows it down to $2^{15}$. Now we can do start looking at particular examples and see if we can find a trend.
Example $1$: using $2$ zeroes
For $2$ zeroes then we only have one possible pairing which is both zeroes together. There are $15$ of these. (Place the first zero anywhere and the next one directly after it, this works for all positions except when the first zero is placed in last place)
Example $2$: using $4$ zeroes
For $4$ zeroes we have $2$ possible pairings, either $4$ together or $2$ and $2$ seperately. Lets do the $4$ together first. Through the same reasoning as above we have $13$ of these. Now the other type would mean first choosing the position of the first pair of which there are $15$ choices. 
$$1111111001111111$$
Notice that after we choose where to place the first pair we have to choose where the next pair should be but for a smaller binary number. We can now generally define a recurrence relation.
Let  $N_k(n)$ denote the number of $k$ digit binary numbers with $n$ pairs of zeros. Then $$N_k(n) = N_{k-2}(n-2) + N_{k-3}(n-2) +... = \sum_{i=2}^{k+2 - n}N_{k-i}(n-2) $$
Now since we want to find this for any number of pairs of zeros, then what you are looking for is $$\sum_{n=0}^8N_{16}(n)$$
Problem 2
Using the recursive formula we had in problem 1 but redefining it so it does not allow for consecutive pairs we get this variation $$N_k(n) = \sum_{i=3}^{k+2 - n}N_{k-i}(n-2)$$
So then you just compute $\sum_{n=0}^8N_{16}(n)$ using the new definition
