I came across this problem in hacker earth where we need to find the number of ways a robot can take such that it takes k turns to reach the nth position.
that is if Xi represents the number of steps taken in the ith turn then sigma(x) from 1 to k must be equal to n, the solution to this is pretty straight forward n+k-1 C k-1.
But what if the robot could take any number of turns but each step must be between 1 and k such that the robot reaches the nth position
[ NOTE the robot can move only in the forward direction ]
then sigma Xi=n [ Xi is the no of steps in the ith turn and 1<=Xi<=K], how would you find the number of ways ?