if I know $f(x+1) = 2f(x) + 1$, how do I solve f(x)

Question

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

Answer 1

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.

Answer 2

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 $.

Answer 3

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$.