Permutation & Combination There is a game in which there is a point P and k other points on a plane. To win, we must draw directed lines starting from point P and ending at point P with exactly n number of lines to be drawn. P can also come in between. 
Example: $n=2$, $k=4$
suppose points are $k_1$, $k_2$, $k_3$, $k_4$.
possible combinations of winning:
$$
P\to k_1\to P
$$
$$
P\to k_2\to P
$$
$$
P\to k_3\to P
$$
$$
P\to k_4\to P
$$
Hence answer is $4$.
Example: $n=3$, $k=2$
suppose points are $k_1$, $k_2$.
possible combinations of winning:
$$
P\to k_1\to k_2\to P
$$
$$
P\to k_2\to k_1\to P
$$
Hence answer is $2$.
Example: $n=4$, $k=2$.
suppose points are $k_1$ and $k_2$.
$$
P\to k_1\to P\to k_2\to P
$$
$$
P\to k_1\to k_2\to k_1\to P
$$
$$
P\to k_1\to P\to k_1\to P
$$
$$
P\to k_2\to P\to k_2\to P
$$
$$
P\to k_2\to P\to k_1\to P
$$
$$
P\to k_2\to k_1\to k_2\to P
$$
Hence answer is $6$.
How do I generalize the result for arbitrary $n$ and $k$?
 A: Strip off the beginning and terminal $p$. So we want to count the sequences of length $n-2$ that do not begin or end with $p$, and such that successive terms of the sequence are different.  
For fixed $k$, let $g_k(n)$ be the number of such sequences (good sequences) of length $n-2$.  
We find a recurrence for $g_k$. Any good sequence $s$ of length $n-2$ can be extended to a good sequence of length $n-1$ by adding any one of the $k-1$ objects that $s$ does not end with.
The only other way to make a good sequence of length $n-1$ is to take a good sequence of length $n-3$, then append  a $p$, and then any of the $k$ objects. Thus
$$g_k(n+1)=(k-1)g_k(n)+kg_k(n-1).$$
The above recurrence is linear homogeneous with constant coefficients. So it can be solved by the method of characteristic equations. In this case the equation is $x^2-(k-1)x-k$. The solutions of the recurrence are therefore of the shape $A_kk^n+B_k(-1)^n$, where we choose $A_k$ and $B_k$ to satisfy the initial conditions. 
These initial conditions can be taken to be  $g_k(2)=k$, and $g_k(3)=k(k-1)$.   Now we can compute $A_k$ and $B_k$, and get a closed-form formula for $g_k(n)$.
It turns out that $A_k=\frac{1}{1+k}$ and $B_k=\frac{k}{1+k}$. Thus
$$g_k(n)=\frac{k^n}{1+k}+(-1)^n\frac{k}{1+k}.$$ 
Remark: The characteristic equation is so simple that we are undoubtedly missing something obvious. But it is sometimes hard to look for a nicer solution once one has found a solution. 
