Prove that transitive closure has at the most $n^2$ elements

Question

Given a relation $R \subseteq A \times A$ with $n$ tuples, I am trying to prove that its transitive closure $R^+$ has at the most $n^2$ elements.

My initial idea was to use the following definition of the transitive closure to identify an argument why the statement to be proven must be true:

$$R^+ = R \cup R^2 \cup R^3 \cup \ldots$$

where $R^k, k \in \mathbb{N}$ stands for the k-fold composition of $R$, but that didn't give me any useful hint to continue the prove. I appreciate any hint that may help me on.

Answer 1

For each ordered pair of different tuples $\{(a,b),(b,c)\}$ we have to add at most one tuple, namely $(a,c)$.

Since there are at most $n(n-1)=n^2-n$ of such pairs, then $|R^+|\le n+n^2-n$

Answer 2

Suppose that it's true for $n = 1...K-1$, then add a tuple to your $n = K-1$ tuples $R$. $(R \cup \{(a,b)\})^+ = R^+ \cup \{(a,x) : (b,x) \in R^+\} \cup \{(x,b): (x,a) \in R^+\} \cup \{(a,b)\} = R'^+$. So since by inductive assumption $|R^+| \leq (K-1)^2 = K^2 - 2K +1.$, we have that $|R'^+|$ is no greater than $3K^2 -2K + 2$. Okay, that's larger than your required bound, but since induction gave us that maybe you can find a proof by induction. That is my answer.