Mi Última Respuesta
He descubierto un menos trivial aproximación de la tasa de crecimiento de $f(n)$. Pero primero quiero ser rigurosos acerca de exactamente lo $f(n)$ está contando. Estoy haciendo esto en el caso que he interpretado mal la pregunta. Mi entendimiento es que el $f(n)$ es el número máximo de distintos pares de $(i, j)$ $1 \leq i < j \leq n$ de manera tal que exista un conjunto de $n$ enteros positivos $\{a_1, a_2, \dots, a_n\}$ $a_i + a_j = s^2$ algunos $s$. Claramente, $f(n) \leq {n \choose 2}$, ya que podemos elegir en la mayoría de las ${n \choose 2}$ pares de $n$ objetos.
Ahora, para encontrar un límite inferior para $f(n)$, sólo tenemos que encontrar un conjunto de pares y de un correspondiente conjunto de valores, de tal manera que todos los valores indexados por los pares de la suma de los cuadrados perfectos. Vamos a considerar el conjunto de $\{1, 2, 3, \dots, n\}$ y definen $h(n)$ como el número de los distintos pares de elementos de este conjunto, que se agregan a los cuadrados perfectos. Claramente $h(n) \leq f(n)$. Ahora voy a plantear una muy simple prueba de demostración de que:
$$n^{\frac32} \sim h(n)$$
Considerar la adición de $n+1$ para el conjunto de $\{1, 2, 3, \dots, n\}$. Ahora nos forma a todos los pares de $(1, n+1), (2, n+1), \dots, (n, n+1)$ cuyo importe correspondiente se $n+2, n+3, \dots, 2n+1$. Ahora, vamos a $s(a, b)$ denotar el número de cuadrados perfectos en el intervalo de $[a, b]$. Entonces tenemos:
$$h(n+1) = h(n) + s(n+2, 2n+1)$$
Ahora, ¿cuántos cuadrados perfectos se encuentran en el intervalo de $[n+2, 2n+1]$? Así, aproximadamente hay:
$$\sqrt{2n+1} - \sqrt{n + 2} \approx \sqrt{2n} - \sqrt{n} = \sqrt{n}(\sqrt{2} - 1)$$
Así, a grandes rasgos, tenemos:
$$h(n+1) \approx h(n) + \sqrt{n}(\sqrt{2} - 1)$$
La expansión de la recursividad y factorizando los $(\sqrt{2} - 1)$ entonces tenemos:
$$h(n) \sim \sqrt{1} + \sqrt{2} + \dots + \sqrt{n} \sim \int_1^n \sqrt{x}\,dx \sim n^{\frac32}$$
A mi las matemáticas aquí no es de mi costumbre estándar de rigor, pero creo que es el sonido. Esto implicaría que la tasa de crecimiento de $f(n)$ está en algún lugar entre el$n^{\frac32}$$n^2$.
Actualización: podemos llegar a un límite inferior para $h(n)$ de una manera diferente, evitando el uso de la integración. Consideremos el conjunto a $\{1, 2, 3, \dots, n\}$. Hay $\lfloor\sqrt{n}\rfloor$ cuadrados perfectos en este conjunto. Para cada cuadrado perfecto,$k^2$, podemos formar con $\lfloor\dfrac{k^2 - 1}{2}\rfloor \geq \dfrac{k^2}{2} - 1$ único pares:
$$(1, k^2 - 1), (2, k^2 - 2), \dots, (\lfloor\dfrac{k^2 - 1}{2}\rfloor, \lceil\dfrac{k^2 + 1}{2}\rceil)$$
Estos no son todos los cuadrados que se pueden formar, pero todos ellos son posibles, por lo que son válidos para un menor enlazado argumento. Deje $R=\lfloor\sqrt{n}\rfloor$ para la facilidad de la notación. El límite inferior es entonces:
$$\sum_{i=1}^{R}\left(\dfrac{i^2}{2} - 1\right) = \frac12\sum_{i=1}^{R}i^2 - R = \dfrac{R(R+1)(2R+1)}{12} - R$$
Es evidente que esto es de la orden de $n^{\frac32}$.
Mi Aburrido Respuesta Original
Voy a dar una muy trivial respuesta a $(2)$. Hemos enlazado:
$$n - 1 \leq f(n)$$
Para ver por qué, elija $a_1 = 1$, y para todos los $i \neq 1$ elija $a_i = i^2 - 1$. Entonces tenemos que para todos los $i \neq 1$, $a_i + a_1 = i^2$. Desde allí se $n - 1$ valores de $i \neq 1 \leq n$, se obtiene el límite inferior.
Actualización: rindiendo homenaje a la comentarista Crostul y el OP ComplexPhi, que han hecho más trabajo de lo que yo, podemos mejorar este límite inferior:
$$f(n) \geq f(k) + n - k$$
para cualquier $k \leq n$.
Destacar el descubrimiento de la entidad Zander anterior, tenemos que $f(4) = 6$, y así tenemos los siguientes obligado:
$$f(n) \geq n + 2 \;\;\; \mathrm{where} \;\;\; (n \geq 4)$$
