# $f_{n+1}(x)=f_n(x+1)-f_n(x)$ functional equation and “classification of functions”

Doing a quiz I found a question of this kind

"given $a_0, a_1, a_2, ...,a_n$ find $a_{n+1}$"

In order to find the $f$ such that $f(a_n)=a_{n+1}$ I tryed for a function like $f(x)=k+x$ for some costant $k$

$$a_{n+1}=k+a_n$$

but the result was not costant...and so I repeated the operation

if the sequence is defined by a function $A(n)=a_n$ I defined a function (sequence) $f$

$$f(n)=A(n+1)-A(n)$$

then applied again to $f$ to obtain $f'$

$$f'(n)=f(n+1)-f(n)$$

this time $f'$ was costant so I was able to find the right answer to the quiz and was even if I know that the next number of the sequence could be every number. Is like asking wich number I'm guessing.

But I'm courious to know if this methoud I used is always usefull if "exist" a real "logic" behind the behavior of a (not-random) sequence of numbers.

What I mean is that for every function on the naturals (or on the reals) $f$ we can define a family of functions

$$f_0(x):=f(x)$$

$$f_{n+1}(x)=f_n(x+1)-f_n(x)$$

For some functions exist one $t$ such that $f_t(x)$ becomes constant and thus $f_{t+1}(x)=0$ so for all the $s>t+1$ $$f_s=f_{t+1}$$ Then we can define the set of all the functions with this property $\mathcal F$.

$$\mathcal F:=\{f: \exists t(t\in \Bbb N)(\forall x f_t(x)=0) \}$$

Note: functions like $cos$ or $sin$ never get constant

So my questions are:

$0$- What are the differences and the terminology of this concept for functions on the reals and functions over the naturals (sequence of natural numbers)?

$1$-How are called the functions in $\mathcal F$ with the property I described? Why are they so "regular"? Whith that I mean: why the procedure $f_n\rightarrow f_{n+1}$ finish for these functions?

$2$-How is called $f_n\rightarrow f_{n+1}$? And can be iterated for non-naturals values (e.g $f_{0,5}$)?

$3$-Exist a way to find the inverse of $f_n\rightarrow f_{n+1}$?

To make more clear what I mean with my third question is since $f_{n+1}$ is the solution of the functional equation

$$\chi(x)+f_n(x)=f_n(x+1)$$

Is known a method to find the solution of this functional equation

$$\chi(b_0)=b_1$$

$$f(x)+\chi(x)=\chi(x+1)$$

• What you are talking about is a discrete version of derivatives. Take a look at this. – dtldarek May 3 '14 at 22:12

$0$- What are the differences and the terminology of this concept for functions on the reals and functions over the naturals (sequence of natural numbers)?

Generally, in the real case, rather than setting $f_{n+1}(x) = f_n(x+1) - f_n(x)$, one usually considers the derivative $f_{n+1}(x) = \frac{d}{dx} f_n(x)$.

$2$-How is called $f_n\rightarrow f_{n+1}$? And can be iterated for non-naturals values (e.g $f_{0,5}$)?

As dtldarek mentions in the comments, your operation is the discrete version of the derivative. I am not sure what you mean for "non-naturals values", but you can certainly let $f_{n+1}(x) = f_{n}(x + \delta) - f_{n}(x)$ for any $\delta > 0$, if your function is defined on all real numbers. This is called a "finite difference" and is useful in approximating the derivative of a function.

$1$-How are called the functions in $\mathcal F$ with the property I described? Why are they so "regular"? Whith that I mean: why the procedure $f_n\rightarrow f_{n+1}$ finish for these functions?

These are polynomials! Note that $f_{n+1}$ always has degree one less than $f_n$, and so the polynomials will eventually finish. On the other hand, if the process finishes (i.e., we eventually arrive at $0$), then the original function must have been a polynomial. To prove this, one uses the discrete analogue of the fundamental theorem of calculus: integration of the $0$ function some number of times will always result in a polynomial (see answer to question 3 below).

$3$-Exist a way to find the inverse of $f_n\rightarrow f_{n+1}$?

Just like when you take the integral of a normal function you get a $+C$, you will have a $+C$ here because $f(x)$ and $f(x) + k$ have the same "derivative" $f(x + 1) - f(x)$ for any $k$. The way you compute $f_n$ given $f_{n+1}$ is as follows: $$f_n(x) = f_{n+1}(0) + f_{n+1}(1) + f_{n+1}(2) + \cdots + f_{n+1}(x-1) + C.$$

One other note

You didn't ask about this, but I wanted to mention it. Binomial coefficients will be very useful in what you're doing here, because $${x +1 \choose k} - {x \choose k} = {x \choose k-1}.$$ In fact, any function $f : \mathbb{N} \to \mathbb{N}$ (where $\mathbb{N}$ contains $0$) can be written uniquely as a sum $$f(x) = a_0 {x \choose 0} + a_1 {x \choose 1} + a_2 {x \choose 2} + a_3 {x \choose 3} \cdots$$ This sum can be infinite, but for a fixed $x$ it is finite since ${x \choose k}$ is eventually $0$. When you write a function in this way, it becomes quite easy to compute the derivative operation $f_n \to f_{n+1}$, or to do the inverse operation $f_{n+1} \to f_n$. This is the discrete analogue of the Power Rule and of Taylor Series.

• Thank for the really clear answer...but.. Don't "hate me" but I'm going to edit my question $2$ and add some details on question $3$ because I already came with a solution of that functional equation but I can't translate it in your explaination about the $+C$ (I don't know Integrals and derivative). – MphLee May 4 '14 at 7:29
• @MphLee Sorry, this answer must be very confusing for you if you do not know derivatives! But do you understand the formula $f_n(x) = f_{n+1}(0) + f_{n+1}(1) + f_{n+1}(2) + \cdots + f_{n+1}(x-1) + C$? $C$ is just some constant; it could be $2$ or $3$ or $27$. There is no way to determine what $C$ is if you only know $f_{n+1}$ and do not know $f_n$. – 6005 May 4 '14 at 7:41
• In few hours I'll add more details! Btw yes, I think I can understand why, is like you're defining a function by recursion, you have to set the starting value.So using the common notation $\Delta^{-1}[f_n]=f_{n-1}$ we chose a pair of values such that $f_{n-1}(\beta_0)=\beta_1$ then the following should hold $(f_{n-1}+f_n)(x)=f_{n-1}(x+1)$ $$f_{n-1}(\beta_0 +1)=f_n(\beta_0)+\beta_1$$ $$f_{n-1}(\beta_0 +2)=f_n(\beta_0)+f_n(\beta_0+1)+\beta_1$$ $$f_{n-1}(\beta_0 +n)=\sum^{n-1}_{i=0}f_n(\beta_0+i)+\beta_1$$ – MphLee May 4 '14 at 8:10
• But in that way $f_{n-1}$ is defined only for few numbers...$\{\beta_0+n:n \in \Bbb N\}$ what about extending it to the real numbers?. And thus $\Delta^{-1}[f]$ is not unique. There is a method to obtain such uniqueness up to some starting values $\beta_0,\beta_1$? Is $\beta_1$ the $C$ your talking about and why is related to the integral? – MphLee May 4 '14 at 8:15
• @MphLee $\beta_1$ is the $C$, yes. It just means a constant. The same thing happens in an integral where you "have to set the starting value" for the recursion. – 6005 May 4 '14 at 8:18