proof by induction for recurrence relation I have the  following question:
Call set $S$ of $[n]$ unfriendly if it contains no two consecutive numbers. 
$E.g$ for $[5]$ = the unfriendly subsets are $\emptyset$, {1},{2},{3},{4},{5}, {1,3},{1,4},{1,5},{2,4},{2,5},{3,5},{1,3,5}.
Let $U(n)$ denote the number of unfriendly subsets of [n]. 


*

*Prove $U(n+2)$=$U(n+1)$+$U(n)$.

*Let $U(n,k)$ denote the number of unfriendly k-subsets of [n]. Prove $U(n,0)=1$, $U(n,1)=n$. and $U(n,2)$=$\binom{n-1}{2}$.

*conjecture  a general formula for $U(n,k)$ and prove it. 
for 1. I have proven for n=1 and assumed true  for all n, but don't know about n+1 case? 
 A: For the first part of the problem, we start with the observation that any unfriendly subset of $[n+2]$ either contains $n+2$ or does not contain $n+2$.
We count the number of unfriendly subsets in each case separately.
We first count all unfriendly subsets of $[n+2]$ that contain $n+2$. We do this by establishing a bijection between unfriendly subsets of $[n]$ and those that we just described. Note that by adding $n+2$ to each of the unfriendly subsets of $[n]$, we get unfriendly subsets of $[n+2]$. Conversely, every unfriendly subset of $[n+2]$ certainly does not contain $n+1$ and by removing $n+2$ from each of them, we get unfriendly subsets of $[n]$. This means that the number of unfriendly subsets of $[n+2]$ that contain $n+2$ is equal to the number of unfriendly subsets of $[n]$ (which is equal to $U(n)$, of course).
Now we count unfriendly subsets of $[n+2]$ that do not contain $n+2$. It is clear that each of the sets falling into this category is also an unfriendly subset of $[n+1]$. Therefore, the number of unfriendly subsets of $[n+2]$ that do not contain $n+2$ is equal to the number of unfriendly subsets of $[n+1]$ (which is equal to $U(n+1)$).
Therefore, we arrive at $U(n+2)=U(n+1)+U(n)$ for each $n\in\mathbb{N}$.
Now, by a similar argument, we have
$$U(n,k)=U(n-1,k)+U(n-2,k-1)$$
for valid $n$ and $k$.
It is clear that $U(n,0)=1$ since the only unfriendly $0$-subset of $[n]$ is the null set.
Note that all singleton subsets of $[n]$ are unfriendly, and therefore $U(n,1)=n$. 
The above recurrence relation for $U(n,k)$ can be rewritten as 
$$U(n-2, k-1)=U(n,k)-U(n-1,k)$$
Summing over $n$, we obtain
$$\sum_{n=k+1}^m \: U(n-2,k-1) = \sum_{n=k+1}^m \:(U(n,k)-U(n-1,k))=U(m,k)-U(k,k)=U(m,k)$$
since $U(k,k)=0$ for all $k\geq 2$. Now, letting $k=2$ gives
$$U(m,2)=\sum_{n=3}^m \: U(n-2,1)=\sum_{n=3}^m \: (n-2) = 1+2+\dots+(m-2)=\binom{m-1}{2}$$
Letting $k=3$ gives
$$U(m,3)=\sum_{n=4}^m \: U(n-2,2)=\sum_{n=4}^m \: \binom{n-3}{2} =\binom{m-2}{3}$$
where we have used the infamous hockey-stick identity in the last step.
Now, it is easy to show (by induction on $k$) that 
$$U(m,k)=\binom{m-k+1}{k}$$ 
