1
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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\}\}$.

$\endgroup$
1
$\begingroup$

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\}$$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.