Note: Problem from "Kenneth Rosen's DM and it's applications" and solution from "Students solution guide for use with ... applications"
Let P(n) be the number of strings not containg two containing two consecutive zeros or two consecutive ones.
I got the answer P(n)=P(n-1)+2P(n-2)+2P(n-3)+...+2P(0) +2
but then the book says the sequence also satisfies the recurrence relation P(n)=2P(n-1)+P(n-2). I am not able to understand this part.