Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given the recursive function:

$$f(0) = \frac{x^2}{2} + \frac{x}{2}, f(n) = \frac{f(n-1)}{2} + \frac{x}{2}$$

where $x$ = some integer

How would one rewrite this function to be strictly non-recursive? Eg. the non-recursive counterpart to the recursive function $f(0) = x$, $f(n) = \large \frac{f(n-1)}{2}$ is $f(x)$ = $\large\frac{1}{2^{x}}$.

Thank you.

share|cite|improve this question
This a linear recurrence relation and there exists techniques for solving them. See here. – Mhenni Benghorbal Jan 2 '13 at 22:35
up vote 2 down vote accepted

$f(n)$ will be a linear function of $x^2$ and $x$. Looking at the first few terms $$f(1)=\frac{1}{4}x^2 + \frac{3}{4}x$$ $$f(2)=\frac{1}{8}x^2 + \frac{7}{8}x$$ etc., it is obvious $$f(n)=\frac{1}{2^{n+1}}x^2 + \left(1-\frac{1}{2^{n+1}}\right)x.$$ You can prove this by induction.

share|cite|improve this answer
Thank you. This is the solution I was looking for. I appreciate it. – user55003 Jan 2 '13 at 23:15

The terminology here is confused. Recursiveness is an intrinsic property of a function itself. Take for example the functions defined as follows:

$$f(0) = 1$$ $$f(n +1) = 2f(n)$$


$$g(n) = 2^n$$

It would be quite wrong to describe $g$ as a "non-recursive counterpart" to $f$. For $g$ is one and the very same recursive function as $f$. And $g$ is recursive precisely because it can be presented in the other way (which shows that $g$ belongs to the class of functions definable from the usual initial functions by composition, recursion and minimization),

We can talk about explicitly recursive vs closed form modes of presentation of a given function. But a function is recursive irrespective of how we present it. Thus take the function defined by

$$\mathit{fermat}(n) = 1 \mathrm{\ iff\ there\ are\ natural\ numbers\ } x, y, z \mathrm{\ such\ that\ } x^{n+3} +y^{n+3} = z^{n+3}$$ $$\mathit{fermat}(n) = 0 \mathrm{\ otherwise}$$

That's a bizarre presentation of what we now know, thanks to Andrew Wiles, is a recursive function -- the everywhere zero function!

share|cite|improve this answer
Ah, thank you for the explanation. You see I only have a minimal grasp on high school algebra, being a young teenager. I knew what I wanted, I was just having trouble wording it so that any mathematician could understand. Thanks, I will keep this information in mind. – user55003 Jan 2 '13 at 23:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.