I was given the following to prove by using bijection:
$F_{n+2} + \sum^n_{k=2} 2^{n-k}F_{k-1} = 2^n$
I know that $F_{n+2}$ is the number of subsets of $[n]$ containing no $2$ consecutive elements, and also that $2^n$ is the number of all possible subsets of $[n]$. So the idea is to prove that the rest of the left term: $\sum^n_{k=2} 2^{n-k}F_{k-1}$ equals the numbers of subsets that contain at least 2 consecutive numbers. But I haven't figured out how to show it yet. Any idea would be appreciated :)