The number of spacing $k$ non-attacking towers on the board $\left\{(i,j):1 \le i \le j \le n \right\}$ 
Prove that the number of spacing $k$ non-attacking towers on the board: $$\left\{(i,j):1 \le i \le j \le n \right\}$$ is equal: $$\left\{\begin{matrix} n+1\\n+1-k\end{matrix}\right\}.$$

This board e.g. for $5$ looks like this:

Unfortunately, in this case I can not give any observations to the exercise, because I completely fell over how I can go about them and I have no imagination to consider this problem. I know only what this board looks like.Can I ask you for some tips on what to look for to start this task?
Thank you in advance for any ideas!    
 A: This can be done by induction (by $k$).
I left base of induction for you. 
Induction step
From Stirling number properties we know identity:
$$\left\{\begin{matrix} n\\i\end{matrix}\right\} = i \cdot \left\{\begin{matrix} n-1\\i\end{matrix}\right\} + \left\{\begin{matrix} n-1\\i-1\end{matrix}\right\} $$
Our cheeseboard is just triangle.
We have:
$$(n-(k-1)) \cdot \left\{\begin{matrix} n\\n-(k-1)\end{matrix}\right\} + \left\{\begin{matrix} n\\n-k\end{matrix}\right\} $$
Explanation:
$(n-(k-1)) \cdot \left\{\begin{matrix} n\\n-(k-1)\end{matrix}\right\}$ - if we put $1$ rook (tower) in top row - then we choose our place in $(n-(k-1))$ ways and from induction rest of rooks put in $\left\{\begin{matrix} n\\n-(k-1)\end{matrix}\right\}$ ways 
$\left\{\begin{matrix} n\\n-k\end{matrix}\right\}$ - if we don't put k'th rook (tower) to top row, we should put all $k$ rooks in our triangle without top row.
This gives us:
$$(n-(k-1)) \cdot \left\{\begin{matrix} n\\n-(k-1)\end{matrix}\right\} + \left\{\begin{matrix} n\\n-k\end{matrix}\right\} = \left\{\begin{matrix} n+1\\n+1-k\end{matrix}\right\} $$
