Who has to buy the beer? There are $115$ members in a team in which everyone has a smart phone. No member of the team wishes to buy beer for every other member of the team. But one Friday, after the work hours, everyone expresses the desire to have beer. The team leader proposes a game, which everyone accepts to play.
The game is that one team member would send a message "Beer" to one of the other team members, who has to forward it to some one other than the person from whom he/she received the message. At the end of the game whoever is the last person to be with the message has to buy beer for everyone else.
Someone arbitrarily sets a time-limit for the game. The team leader starts the game by sending the message to someone of his/her team. Assuming that anyone in the team could send message to anyone without any difficulty, what is the probability that at the end of the game, when $2009$ messages have been passed, it's the team-leader who is found to be the one with the last message, and hence, the one to buy beer for everyone else?
So, there are $115$ vertices and there is an edge from one to every other vertex. The graph is, thus, $114-$regular and simple. So, the problem is actually this: Can there be a path starting from a vertex $u$ and after having traversed $2009$ edges, such that one can not leave a vertex by the same edge one came from, culminating back to $u$? Since, the path $u-u$ must contain some cycle, which can be of length $3$ to $115$,the question is does there exist a non-negative solution of:
$2x_1+3x_2+...+115x_{114}=2009$
such that such a $u-u$ path exists? For instance, $x_1=1000$ and $x_2=3$ can not be a solution as it would imply that one took the edge $v-v$, $v\in V(G)$, consecutively which is not allowed.
How do we solve this?

I don't understand the method you are attempting but here is a solution to the problem.  Consider all sequences
$$x_0,x_1,\ldots,x_n$$
with $n$ steps, of the type you are considering: that is
$$x_k\in\{1,\ldots,115\},\ x_0=1,\ x_k\ne x_{k-1},\ x_k\ne x_{k-2}.$$
We wish to find $P(x_n=1)$ in the case $n=2009$.
I will assume that people do not "target" the leader as suggested in other comments but that they choose at random from all available possibilities.
Let $p_n$ be the probability of obtaining $x_n\ne1$ and $x_{n-1}\ne1$ in such a sequence.  The answer to your problem is
$$\frac{p_{2008}}{113}\ .$$
Now for $n\ge4$ we have
$$\eqalign{p_n
  &=P(x_n\ne1,\,x_{n-1}\ne1,\,x_{n-2}\ne1)
    +P(x_n\ne1,\,x_{n-1}\ne1,\,x_{n-2}=1)\cr
  &=\frac{112}{113}p_{n-1}+P(x_{n-1}\ne1,\,x_{n-2}=1)\cr
  &=\frac{112}{113}p_{n-1}+P(x_{n-2}=1,\,x_{n-3}\ne1,\,x_{n-4}\ne1)\cr
  &=\frac{112}{113}p_{n-1}+\frac{1}{113}p_{n-3}\ .\cr}$$
This recurrence relation, with suitable initial conditions, can be solved in the usual way.  The characteristic equation is cubic: fortunately, $1$ is a root; unfortunately, the other two are messy complex surds.  If my algebra is correct the answer is
$$p_n=\frac1{(1-\alpha)(1-\beta)(\alpha-\beta)}\bigl[(\alpha-\beta)-(1-\beta)\alpha^n+(1-\alpha)\beta^n\bigr]$$
where
$$\alpha=\frac{-1+i\sqrt{451}}{226}\ ,\quad
  \beta=\frac{-1-i\sqrt{451}}{226}\ .$$
Evaluation by Maple gives the answer
$$\frac{p_{2008}}{113}=0.008695652174$$
which is very close to $\frac1{115}$.  This is to be expected since, as pointed out in other comments, any initial effects reducing (or increasing) the chance of the leader buying the beers should have almost disappeared by the $2009$th step.
