title: Understanding How Many Times Nested Loops Will Run
body: <p>I am trying to understand how many times the statement "x = x + 1" is executed in the code below, as a function of "n":</p>
  
  <pre><code>for (i=1; i&lt;=n; i++)
    for (j=1; j&lt;=i; j++)
      for (k=1; k&lt;=j; k++)
         x = x + 1 ;
  </code></pre>
  
  <p>If I am not wrong the first loop is executed <em>n</em> times, and the second one <em>n(n+1)/2</em> times, but on the third loop I get lost. That is, I can count to see how many times it will be executed, but I can't seem to find the formula or explain it in mathematical terms.</p>
  
  <p>Can you?</p>
  
  <p>By the way this is not homework or anything. I just found on a book and thought it was an interesting concept to explore.</p>