Cardinalità di un insieme discreto

"hydro":

---

Non capisco esattamente quale risposta tu stia cercando; se vuoi una formula polinomiale non credo proprio che esista.

Asintoticamente $S_n$ ha ovviamente $n^2$ elementi. Puoi anche stimare l'errore perchè chiaramente $|S_n|$ la puoi calcolare così: se $x\ge \text{ceil}2\sqrt{n}$ vanno bene tutte le scelte di $y$, quindi hai $n(n-\text{ceil}2\sqrt{n})$ elementi. Altrimenti, per ogni scelta di $x$ hai $\text{floor}\frac{x^2}{4}$ scelte di $y$. In totale quindi $|S_n|=n(n-\text{ceil}2\sqrt{n})+\sum _{x=1}^{\text{ceil}2\sqrt{x}-1}\text{floor}\frac{x^2}{4}$. Adesso puoi stimare quella sommatoria da sotto e da sopra levando le parti intere e troverai che l'errore è dell'ordine di $n\sqrt{n}$ (a meno di qualche strana cancellazione, nel qual caso bisogna pensarci meglio).

"Mathita":

---

@hydro, non ho ancora esaminato le modifiche che hai apportato, ma intanto ti ringrazio!

Nello spoiler riporto il ragionamento che ho seguito per trovare la mia soluzione.

Riprendo un attimo le notazioni. L'obiettivo è determinare la cardinalità dell'insieme

$S_n=\{(x,y)\in N\times N:x^2-4y\ge 0\}$.

Osservo preliminarmente che, per ogni $n\ge 1$, gli insiemi ${1,2,...,n}^2$ e ${1,2,...,n,n+1}^2$ differiscono di $(n+1{)}^2-n^2=2n+1$ elementi. Dal punto di vista geometrico, partendo dal "quadrato puntato" ${1,2,...,n}^2$, possiamo costruire il "quadrato puntato" ${1,2,...,n,n+1}^2$, aggiungendo i $2n+1$ punti di coordinate intere

$(n+1,k)$ con $k\in 1,2,...,n+1$

$(k,n+1)$ con $k\in \{1,2,...,n\}$

Inoltre, evidentemente $S_n\subseteq S_{n+1}$, per ogni $n\ge 1$.

Una volta stabilito il set-up, osservo quanto segue.

Per $x\ge 1$, la parabola di equazione $y=\frac{x^2}{4}$ giace al di sopra della bisettrice del 1° e del 3° quadrante se e solo se $x\ge 4$. (Dimostrazione ovvia.). Ciò prova che per ogni $n>4$, $n<\frac{n^2}{4}$ o equivalentemente $2\sqrt{n}<n$. Dal punto di vista geometrico ciò si traduce in: per ogni $n>4$, la parabola fugge dal quadrato $[1,n{]}^2$ intersecando internamente il segmento che congiunge i punti $(1,n)$ e $(n,n)$ (in pratica il segmento superiore del quadrato).

Questo ci permette di affermare che per ogni $n\ge 4$, l'insieme $S_{n+1}$ si esprime nell'unione di tre insiemi a due a due disgiunti:

$S_{n+1}=S_n\cup \{(n+1,k):k\in 1,2,...,n+1\}\cup \{(j,n+1):2\sqrt{n+1}\le j\le n\}$

da cui

$|S_{n+1}|=|S_n|+|\{(n+1,k):k\in 1,2,...,n+1\}|+|\{(j,n+1):2\sqrt{n+1}\le j\le n\}|$

Ora, il secondo addendo è chiaramente $n+1$, un po' meno evidente è il terzo addendo. Sia $\text{ceil}2\sqrt{n+1}$ il più piccolo intero più grande o uguale a $2\sqrt{n+1}$, allora

$|\{(j,n+1):2\sqrt{n+1}\le j\le n\}|=|\{(j,n+1):\text{ceil}2\sqrt{n+1}\le j\le n\}|=$

$=n-\text{ceil}2\sqrt{n+1}+1$

In definitiva $|S_{n+1}|=|S_n|+2n+2-\text{ceil}2\sqrt{n+1}$ per ogni $n\ge 4$ da cui:

$|S_{n+1}|=|S_4|+\sum _{k=4}^n(2k+2-\text{ceil}2\sqrt{k+1})=$

$=7+(n^2+3n-18)-\sum _{k=4}^n\text{ceil}2\sqrt{k+1}=$

$=n^2+3n-11-\sum _{k=4}^n\text{ceil}2\sqrt{k+1}$ per ogni $n\ge 4$, salvo errori o omissioni.

Non una bellissima dimostrazione, lo ammetto. Non mi piace nemmeno come l'ho buttata giù... :\

"Mathita":

---

Ciao a tutti!



Inoltre, se devo essere del tutto sincero, non capisco il ragionamento che fai per le stime asintotiche. Ho l'impressione che ragionando con l'integrale ${\int }_1^{\text{ceil}\sqrt{2n}}\frac{x^2}{4}dx$ tu stia aggiungendo un pezzo: l'area della parte di grafico di $\frac{x^2}{4}$ compresa tra le rette $y=0$ e $y=1$.