- #1

lovemake1

- 149

- 1

## Homework Statement

Given binary string of length n.

substrings of 1's should be even. (given 0 is a delimeter)

eg) 10111 is broken down into 1 and 111 (all odd)

so, for example string with H(n = 4)

0000 1100 0110 0011 1111

there are 5 of them.

H(n = 3)

000 110 011

there are 3 of them.

**Q. Develop a recurrence for H(n), and show why it counts the number of strings correctly.**

## Homework Equations

## The Attempt at a Solution

I have tried to form some kind of pattern but I am still not unable to form a recurrence.

we intuitively know that H(n=0) and H(n=1) are both 0 which is still even.

and H(n=2) = 2 since ( 00, 11) takes place.

I was thinking of setting basecase of recurrence upto n = 4.

so list

H(n)

2 n = 2

3 n = 3

5 n = 4

? n > 4

First of all, am I right to list basecases starting from 2?

and what are some crucial steps I need to take in order to find the right recurrence formula

Helps are much appreacited, thank you

Last edited: