Flea jumping $n\to n+1$ for tails or $n \to n+2$ for heads & renewal theorem This is a question that I should be using renewal theory for, it is to do with a flea that jumps either $n\to n+2$ with probability $p\in[0,1]$ or $n\to n+1$ with probability $1-p$.
I am having difficulty defining the probability that the flea will eventually land on $k$
So call the probability $u_k$, the event that the flea eventually lands on the integer $k$
$\displaystyle u_k=\sum_{l\geq0}^{\lfloor k/2 \rfloor} {k-l \choose l}(1-p)^{k-2l}p^l$
My thoughts were that this could be the probability of having $k-2l$ single jumps and $l$ double jumps. There are always $k-l$ total jumps which obviously changes depending on how many double hops or single hops contribute to landing on the integer $k$. 
Is $\lfloor k/2 \rfloor$ correct for the summation limit? if $k$ is even it doesn't matter, but if it is odd I can't picture what happens.
 A: Well as you said, you should look at what possible pairs of (success/fail) or as you call them (double jump/single jump) would make you end in $k$.
Then for each combination of $(n,d)$ you can calculate the probability of it happening which is $\large{n \choose s}p^d(1-p)^{n-d}$
where $n$ is the number of times you toss the coin and $d$ is the number of double jumps (successes) needed to end in $k$ given the value of $n$.
What you are saying in your formula is right, imo, because what you are saying is that in order to get to an even $k$, you can either do $k$ single jumps or $\frac{k}{2}$ double jumps, or anything in between. And this is indeed given by any number $s$ of single jumps (fails) ranging from $k$ to $0$ or a number $d$ of double jumps (successes) ranging from $0$ to $\frac{k}{2}$.
At anytime you have $k=2d+s$ where $a$ is the number of double jumps and $b$ the number of single jumps. So the total number of jumps is indeed equal to $d+s=k-d$
This concludes that your formula is actually correct for an even $k$ ;)
for $k$ even : $\displaystyle u_k=\sum_{l=0}^{k/2} {k-l \choose l}(1-p)^{k-2l}p^l$
Now, in the case where $k$ is odd, it is simply equivalent to saying that you need to jump to $k-1$ which is even and then make a single jump to get to $k$. The probability of making a single jump is $(1-p)$.
So for $k$ odd : $\displaystyle u_k=(1-p)\times u_{k-1}=(1-p)\sum_{l=0}^{(k-1)/2} {k-1-l \choose l}(1-p)^{k-1-2l}p^l$
A: As it turns out, you can express it in a much nicer way that you currently do.
I'll assume, since you didn't specify, that the flea starts on $n=0$. If the flea starts on $n=1$, then simply consider the value for $k-1$ rather than $k$.
Now, the probability that the flea will land on position $1$ is simply $1-p$, and we take the probability that it will land on position $0$ to be $1$. The probability that the flea will land on position $2$ is then $(1-p)^2+p$ (we can use this for confirmation).
Let us call $u_k$ the probability of the flea landing on position $k$
Now, if we assume that the flea has landed on position $k-2$, there are two ways for the flea to land on $k$: namely, by two single steps ($(1-p)^2$) or by one double-step ($p$). However, the flea may not land on position $k-2$, but skip it in going from $k-3$ to $k-1$. The probability of it not landing on $k-2$ is $1-u_{k-2}$, in which case the flea has a probability $1-p$ of landing on $k$.
So,
\begin{align}
u_k &= ((1-p)^2+p)u_{k-2}+(1-p)(1-u_{k-2})\\
&=p^2u_{k-2}+1-p
\end{align}
We can quickly convert this to be in terms of $u_0$ or $u_1$. Note that $u_2=p^2u_0+1-p = p^2+1-p=(1-p)^2+p$, as expected.
$$
u_k = p^2u_{k-2}+1-p = p^4u_{k-4}+p^2(1-p)+1-p
$$
So, for even $k$, we have
$$
u_k = p^k+(1-p)\left(\sum_{i=0}^{\frac{k}2-1}p^{2i}\right)
$$
For odd $k$, we have
$$
u_k = p^{k-1}(1-p) + (1-p)\left(\sum_{i=1}^{\frac{k-1}{2}-1}p^{2i}\right)
$$
But of course, the sum in the brackets on the right can be written in a much neater way:
$$
\sum_{i=0}^{n-1}p^{2i}=\frac{1-p^{2n}}{1-p^2}
$$
So we can write our functions as, for even $k$,
$$
u_k = p^k+\frac{1-p^k}{1+p} = \frac{p^{k+1}+1}{1+p}
$$
and, for odd $k$,
$$
u_k = p^{k-1}(1-p) + \frac{1-p^{k-1}}{1+p}=\frac{p^{k-1}(1-p^2)+1-p^{k-1}}{1+p}=\frac{1-p^{k+1}}{1+p}
$$
Now, we can write this as a single expression as
$$
u_k = \frac{1-(-p)^{k+1}}{1+p}
$$
As for your expression, it mostly looks right, and I can confirm that it is correct as written (it produces the same result as I obtain above, once simplified).
As for why it has the $\lfloor\frac{k}2\rfloor$, and what's going on in the odd case, think of it this way - there must necessarily be an odd number of single jumps, so that the total distance travelled is odd. As such, the minimum number of single jumps must be $1$, and so $k-2l=1$ is the smallest possible index for $(1-p)$. Of course, this makes $l=\frac{k-1}2=\lfloor\frac{k}2\rfloor$.
As for the request for use of the renewal theorem... I'm confused, as from what I can see, the renewal theorem discusses the asymptotic behaviour of $u_k$, not the values of the $u_k$ themselves.
A: If $u_k$ is the probability of landing on $k$, we have $u_0 = 1, u_1 = 1-p$, and for $n\ge 2$, it can either land with a small jump, which happens with probability $(1-p)u_{k-1}$, or with a long jump, which happens with probability $pu_{k-2}$.
Hence $u_{k} = (1-p)u_{k-1} + p u_{k-2}$, which you can rewrite as $u_{k}-u_{k-1} = (-p)(u_{k-1} - u_{k-2})$. 
Since $u_1-u_0 = (-p)^1$, we have by induction, $u_k - u_{k-1} = (-p)^k$, and with another induction, $u_k = \sum_{i=0}^k (-p)^i = \frac {1-(-p)^{k+1}}{1+p}$
