How to approach an equation of the form $f(x)=y$ where $f$ is recursively defined?

Question

This is a homework problem so I am not looking for someone to solve it for me. I would like to know how I should approach this problem, or in what direction I should research to figure it out myself.

For $y \in \mathbb N$, $y > 1$, find $x$ for which $f(x) = y$. Given:

$f(0)=1$
$f(1)=1$
$f(2)=2$
$f(2x)=f(x)+f(x+1)+x$
$f(2x+1)=f(x)+f(x−1)+1$

Is the formula for f(2x) correct? Is that a "+x" on the end? — marty cohen, Dec 13 '14 at 00:40
For $f(3)$, you need $f(0)$, since $f(2\cdot 1 + 1) = f(1) + f(1-1) + 1$. — Daniel Fischer, Dec 13 '14 at 00:41

score 0 · Answer 1 · answered Dec 13 '14 at 00:44

0

Solve for $1$:

$f(2x+1) - f(x) - f(x-1) = 1 = f(1)$

Solve for $2$:

$f(2) = f(1) + f(2) + 1 = 1 + 2 + 1 = 4 \neq 2$

Contradiction

answered Dec 13 '14 at 00:44

2

The induction formula for f(2x) is for $x \ge 2$. – marty cohen Dec 13 '14 at 00:47
How exactly do we find "x"? – Dec 13 '14 at 00:48

How to approach an equation of the form $f(x)=y$ where $f$ is recursively defined?

1 Answers1