So I was looking into recursive expressions and recently dealt with this expression:
$$ f(i) = q \times (f(i-1)+1) + \bar{q} \times f(i-1) $$
where $q$ is a probability between $0$ and $1$ and $\bar{q} = 1-q$.
A non-recursive formula is quite simple ($ = q \times i$)
But when I change the recursive expression to:
$$ f(i) = q \times (f(i-1)+1) + \frac{\bar{q} \times f(i-1)}{2} $$
the solution I found becomes:
$$ \frac{q-q\times(q+\frac{\bar{q}}{2})}{1-(q+\frac{\bar{q}}{2})} $$
There might be other solutions though. I do find it strange that a relative small change in the recursive expression leads to a significantly more complex non-recursive formula.
I now got another recursive expression:
$$ f(i) = q \times i + \bar{q} \times f(i-1) $$
The solution to this one (again, there are other ones) is:
$$ i-\frac{\bar{q}\times(1-\bar{q}^i)}{q} $$
But now when I do the same 'thing' as with the other expression:
$$ f(i) = q \times i + \frac{\bar{q} \times f(i-1)}{2} $$
I get completely stuck in finding a solution (i.e. a non-recursive formula).
Does anyone have an idea to solve this recursion or any hints?
Since I am unfamiliar with generating functions, I am forced to ignore the comment of ancientmathematician, and proceed very inelegantly.
Assume that $f(0) = 0$ and let $r = \frac{1-q}{2}.$
Then:
$f(1) = q.$
$f(2) = 2q + rq.$
$f(3) = 3q + r(2q + rq) = 3q + 2rq + r^2q.$
Inductively assume that
$$f(n) = \sum_{k=1}^n qkr^{(n-k)}.$$
Then
$$f(n+1) ~=~ (n+1)q + \sum_{k=1}^n qkr^{([n+1] - k)} ~=~ \sum_{k=1}^{n+1} qkr^{([n+1]-k)}.$$