if I know $f(x+1) = 2f(x) + 1$, how do I solve f(x) This is just my thought on run time of a binary search:
if you are allowed to make 1 comparison, you can search a sorted list of length 1, but if you are allowed to perform 2 comparisons, you can search a list of length 3 (if the list is sorted [1,2,3], you first search the middle [2] and depends on the result, you continue down the left[1]/right[2], which is just a sorted list of length one)
it is pretty obvious that when you are given an extra comparison, the length of the sorted list you can search is doubled + 1
$f(x+1) = 2f(x) + 1$
I want to represent $f(x)$ in terms of x, the relation between list length and number of comparison required.
the answer is $$f(x) = 2^x -1$$ However, I want to solve it using math...but I don't remember how to solve a recursively defined function like this
thanks
 A: Let $g(x)=f(x)+1$. Then
$$
g(x+1)=f(x+1)+1=2f(x)+1+1=2(f(x)+1)=2g(x).
$$
This suggests a representation of the form $g(x)=g(0)2^x$ so that $f(x)=g(x)-1=g(0)2^x-1$. 
Conversely, you can check that all $f(x)=c2^x-1$ satisfy your functional equation.
A: We can use some insight from differential equations (if we're familiar with that).
After subtracting $f(x)$ from both sides the equation becomes
$$
f(x+1) - f(x) = f(x) + 1. \tag{1}
$$
Let
$$
\Delta f(x) = f(x+1) - f(x)
$$
be the discrete derivative, also known as the first forward difference.  Equation $(1)$ becomes
$$
\Delta f = f + 1. \tag{2}
$$
We will first solve the homogeneous equation
$$
\Delta f = f, \tag{3}
$$
then combine combine this with a particular solution of $(2)$ to get the general solution to the equation.
Just as the exponential function $y(x) = e^x$ satisfies $y' = y$, the function $f(x) = 2^x$ satisfies $\Delta f = f$. Thus, the general solution of $(3)$ is
$$
f_\text{hom}(x) = A2^x
$$
for any constant $A$.
It is easy to see that a particular solution of $(2)$ is
$$
f_\text{part}(x) = -1,
$$
so the general solution to $(2)$ is given by
$$
f(x) = f_\text{hom}(x) + f_\text{part}(x) = A2^x - 1.
$$
At the top of your post you specified that

if you are allowed to make 1 comparison, you can search a sorted list of length 1

and this is equivalent to requiring
$$
1 = f(1) = 2A - 1
$$
and thus $A = 1$.  Finally, the solution to your recurrence is
$$
f(x) = 2^n - 1.
$$

Bonus round.
Defining the second difference
$$
\Delta^2 f(x) = \Delta(\Delta f(x)) = f(x+2) - 2f(x+1) + f(x),
$$
show that the Fibonacci recurrence
$$
f(x+2) = f(x+1) + f(x)
$$
is equivalent to the second order discrete differential equation
$$
\Delta^2 f + \Delta f - f = 0. \tag{4}
$$
Show also that, if $g(x) = (1+r)^x$, then
$$
\Delta g(x) = r g(x)
$$
and
$$
\Delta^2 g(x) = r^2 g(x).
$$
Use these properties and equation $(4)$ to obtain the expression for the Fibonacci numbers from Ant's comment.
Hint: If you were trying to solve the ordinary differential equation
$$
y'' + y' - y = 0,
$$
you would substitute $y(x) = e^{rx}$ and solve for $r$.
A: Suppose
$f(x+1)
=af(x)+b
$.
We want to "adjust" $f$
so the adjusted function $g$
satisfies
$g(x+1) = ag(x)$,
since we know how to solve this.
The simplest adjustment
is to add a constant
to $f$.
So,
let
$g(x) = f(x)+c$,
where we want to determine $c$
so that
$g$ is "nice".
Then
$f(x) = g(x)-c$,
so
$g(x+1)-c
=a(g(x)-c)+b
=ag(x)-ac+b
$,
or
$g(x+1)
=ag(x)-ac+b+c
=ag(x)-c(a-1)+b
$.
To make this
become nice,
choose $c$
such that
$b-c(a-1) = 0$
or
$c = \frac{b}{a-1}
$.
Then
$g(x+1)
=ag(x)
$,
so
$g(x) = a^x g(0)$
(or $g(x) = a^{x-1}g(1)$),
or
$f(x)+c
=a^x(f(0)+c)
$
(or
$f(x)+c
=a^{x-1}(f(1)+c)
$
)
or
$f(x)
=a^x(f(0)+c)-c
$
(or
$f(x)
=a^{x-1}(f(1)+c)-c
$
).
In your case,
$a=2$ and $b=1$,
so
$c = 1$,
and we get
$f(x)
=2^{x-1}(f(1)+1)-1
=2^{x-1}2-1
=2^{x}-1
$.
