Quoted By:
Let's see how smart you anons really are...
Implement the following python function:
```Python
def bits(n, k):
```
That determines in how many n-bit sequences a bit to 1 only appears in sequences of at least k 1s in a row.
For example, if n = 3 and k = 2 then we have 4 valid sequences, namely: 000, 110, 011 and 111.
If n = 4 and k = 3 then we also have 4 valid sequences, namely: 0000, 1110, 0111 and 1111.
If n = 4 and k = 2 then we already have 7 valid sequences - besides the 4 previous ones we now also have: 1100, 0110 and 0011.
If n = 8 and k = 2, then we have valid sequences 65.
If n = 5 and k = 3, then we have valid sequences 7.
Try using exhaustive search algoritms.
