Example: Numbers Without Consecutive 1s in binary representation

• We observe that for n = 1, we have 0 and 1 => n(1) = 2

• for n = 2, we have 00, 01, 10, 11 => n(2) = 3

• for n = 3, we had a 0 to the sequence of n = 2 and we have the same number p(n-1), then we add 1 to the same sequence, and we observe that this is creating a fibonacci sequence:

• 0

• 1

  • 2

---

• 00
• 01
• 10
• 11
  • 3

---

• 000

• 001

• 010

• 011

  • 3 => p(n-1)

• 100

• 101

• 110

• 111

  • 2 -> p(n-2)

maxNumWithoutConsecutiveOnesBinary(n)
    d(1) = 2
    d(2) = 3

    for i = 3 to n
        d[i] = d[i-1] + d[i-2]