How do I mathematically express a set generated using two loop variables within a single for loop?

Question

I don't know the proper mathematical expression for for-loops, especially those that carry two distinctly behaving variables with each iteration.

For example, assuming n is previously defined and holds some positive integer, how I would I represent the set printed by this for-loop in mathematical notation?

// prints a set of multiples (n previously defined)
for (int j=n, k=n; k>=0; j++, k--) {
  cout << (n-j)*(n-k) << endl;
}

Forgive my crudeness, but I'm thinking something along the lines of:

$\left \{ \left ( n-j \right ) \cdot \left ( n-k \right )\forall j \left \{ n, n+1, ..., 2n \right \} \forall k \left \{ n, n-1, ..., 0 \right \}\right \}$

I'm lost. Should I even be using $\forall$ in this context? Any guidance is greatly appreciated!

Answer 1

You attempt is basically correct, assuming that the for-loop is short for nested loops. You'd usually write it like

$\qquad\displaystyle\{ (n-j)(n-k) \mid j \in \{n, \dots, 2n\}, k \in \{n, \dots, 0\}\}$.

Now we note that we can write

• $k$ instead of $n-k$ (in the code, reverse the direction of the for-loop) and
• $-j$ with $j \in \{0, \dots, n\}$ instead of $n-j$ with $j \in \{n, \dots, 2n\}$ (do you see why?).

So we get

$\qquad \displaystyle \{ -jk \mid j, k \in \{0, \dots, n\}\}$.

---

If, on the other hand, the for-loop is supposed to step j and k simultaneously, building all combinations is not what happens. Then, you'd have

$\qquad\displaystyle \{ (n-j)(n-k) \mid (j,k) \in \{ (n,n), \dots, (2n,0) \} \} $

which we can rewrite by noting that

• $j \in \{n, \dots, 2n\} \iff (n-j) \in \{0, -n\}$ and
• $k \in \{n, \dots, 0\} \iff (n-k) \in \{0, n\}$ and

to

$\qquad\displaystyle \{ -jk \mid (j,k) \in \{(0,0), \dots, (n,-n)\} \}$.

But now $j$ and $k$ only differ by the sign, so we can rewrite using only one variable:

$\qquad\displaystyle \{ -x^2 \mid x \in \{0, \dots, n\}\}$.

Answer 2

If you go and execute the program you wrote you will get the sequence $0, -1, -4, -9, -16, \dots$. The program prints the first $n+1$ squares negated. In set theory, one would write $$\{-x^2:0\le x \le n\}$$.

Answer 3

In your pseudocode it seems to me like you are enumerating the set $$\{0\cdot 0,-1\cdot1,\ldots,-n\cdot n\}=\{-i^2\mid 0\leq i\leq n\}$$ In your mathematical set notation you seem to be making the set $$\bigcup\limits_{i=0}^n\{i\cdot -j\mid 0\leq j\leq n\}$$ If you only have one for loop then you may only have one dependent variable (the first case) and you therefore only need a single $\forall$ quantifier in your description of the set.