On a lower bound for the birthday problem I'm now familiar with a lower bound for the birthday problem as exposed in the theorem A.16 of Katz and Lindell book (alternatively see this webpage).

If one denotes by $C(q,N)$ the probability of collision when taking elements independent and uniformly distributed from a set of size $N$ The bound is obtained by assuming $q \le \sqrt{2N}$:

$C(q,N) \ge \frac{q(q-1)}{4N}$

However, the bound that I has been hold in my class is (without the inequality assumption in $q$):

$\forall N \in \mathbb{N}.C(q,N) \ge \frac{(q-1)^2}{2N}$

How can I prove this bound correct?
The question's $\displaystyle C(q,N) \ge \frac{(q-1)^2}{2N}$ bound is wrong. That's incompatible with the well-known fact that for $N=q^2$ and large, $C(q,N)\approx1-e^{-1/2}\approx39.3\%$.

A correct bound is $\displaystyle C(q,N) \le \frac{(q-1)\,q}{2N}$, valid for all $q$ and $N\ge1$, and tight when $q\ll\sqrt N$.

Another correct bound is $\displaystyle C(q,N) \ge \frac{(q-1)^2}{4N}$ when $1\le q\le\sqrt{2N}$, which follows from the question's lemma.

See this answer for some derivations, but beware that the notation there is $(n,k)$ and $p_n$ where the question has $(q,N)$ and $C(q,N)$.