So I was interested in the following function's domain:


So I started just looking at small values of $n$ and seeing the lengths of the domains and the actual domains themselves.

$$\operatorname{Dom{[f_1(x)]}}=(-\infty,1]\rightarrow |\operatorname{Dom{[f_1(x)]}}|=\infty$$

$$\operatorname{Dom{[f_2(x)]}}=[1,2]\rightarrow |\operatorname{Dom{[f_2(x)]}}|=1$$

$$\operatorname{Dom{[f_3(x)]}}=[-1,2]\rightarrow |\operatorname{Dom{[f_3(x)]}}|=3$$

$$\operatorname{Dom{[f_4(x)]}}=[0,4]\rightarrow |\operatorname{Dom{[f_4(x)]}}|=4$$

$$\operatorname{Dom{[f_5(x)]}}=[-11,5]\rightarrow |\operatorname{Dom{[f_5(x)]}}|=16$$

$$\operatorname{Dom{[f_6(x)]}}=[-19,6]\rightarrow |\operatorname{Dom{[f_6(x)]}}|=25$$

$$\operatorname{Dom{[f_7(x)]}}=[-29,7]\rightarrow |\operatorname{Dom{[f_7(x)]}}|=36$$

$$\operatorname{Dom{[f_8(x)]}}=[-41,8]\rightarrow |\operatorname{Dom{[f_8(x)]}}|=49$$

$$\operatorname{Dom{[f_9(x)]}}=[-55,9]\rightarrow |\operatorname{Dom{[f_9(x)]}}|=64$$

So outside the first couple of upper bound values, it seems then that the upper bounds of the domain of $f_n(x)$ is $n$ itself while the length of the domain seems to be $(n-1)^2$.

I looked up the sequence of upper bounds in the OEIS and there was no pattern associated with it and so I wondered if there was a closed form for the upper bound of $f_n(x)$ and same for the length. Looking up the sequence $\{1,3,4,16,25,36,49,64,...\}$ in OEIS gives no resultant pattern, and again was wondering if there is a closed form expression for the length of the domain of $f_n(x)$.

Is there a better approach to determining a sequence of upper and lower bounds for this function and is there a more rigorous way to determine exactly the domain of the $n$th function?


EDIT: There was an error in my original solution, I incorrectly said the Domain was (for $n \ge 5$)

$$\text{Dom}[f_n(x)] = [n-n^2,n]$$

when the right answer is

$$\text{Dom}[f_n(x)] = [n-(n-1)^2,n]$$

It doesn't change the nature of the proof, but I've corrected it below.

Once can prove with mathematical induction that

$$\text{Dom}[f_n(x)] = [n-(n-1)^2,n]$$

holds for $n\ge 5$.

They key idea is the recursion

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

That means in order to determine $\text{Dom}[f_{n+1}(x)]$, we must determine when $\sqrt{n+1-x}$ is defined and when $\sqrt{n+1-x} \in \text{Dom}[f_{n}(x)]$.

That means

$$\text{Dom}[f_{n+1}(x)] = (-\infty,n+1] \cap \{x: \sqrt{n+1-x} \in \text{Dom}[f_{n}(x)]\}$$

This formula, starting with the known $\text{Dom}[f_1]=(-\infty,1]$, generates the sequence as given in the question. It is easy to check by hand that the given sequence is correct for $n=1,2,3,4$ and $5$. This proves the start of the inductive process ($n=5$).

Now to the inductive step: Assume the forumula is correct for $n=k$. We now know that

$$\text{Dom}[f_{k+1}(x)] = (-\infty,k+1] \cap \{x: \sqrt{k+1-x} \in \text{Dom}[f_k(x)]\}$$

By the induction hypothesis $\text{Dom}[f_k(x)]=[k-(k-1)^2,k]$. Since $k\ge 5$, we have $k-(k-1)^2 \le 0$. That means $\sqrt{k+1-x} \in [k-(k-1)^2,k]$ is equivalent to

$$\sqrt{k+1-x} \le k$$

which is equivalent to

$$ 0 \le k+1-x \le k^2$$

which is equivalent to

$$(k+1)-(k+1-1)^2= -k^2+k+1 \le x \le k+1$$

Since $[-k^2+k+1,k+1] \subset (-\infty,k+1]$, we proved what we wanted to prove in the induction step:



The straightforward approach is to let $x_0 = x$ and $x_{k+1} = \sqrt{n-k - x_k}$ for all $0 \le k < n$. Then $x_n = f_n(x)$ is the desired quantity. It is defined if and only if $x_k \le n-k$ for all $k \ge 0$. By the recursion, all but the first case are equivalent to $\sqrt{n-k - x_k} \le n-k-1$ i.e. $$x_k \ge n-k - (n-k-1)^2 \tag{*}$$ for all $k \ge 0$. In particular, $n - (n-1)^2 \le x \le n$ for $k = 0$.

It remains to show that if $x$ is in this range, then every $x_k$ satisfies $(*)$. Can you go from here? I've got to run, but I'll be back later to update my answer if necessary.

Update: This actually doesn't seem to be very straightforward. Ingix's solution is much better!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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