 <p>proof of Alleo answer:</p> <p>first write your second formula from j to 1</p> <pre><code>k(i,j)= k(i,j-1) + 1 k(i,j-1) = k(i,j-2) + 1 ... k(i,1) = k(i,0) + 1 </code></pre> <p>sum up these formulas you get :</p> <pre><code>k(i,j) = k(i,0) + 1+1 ..+1 = k(i,0) + j (1) </code></pre> <p>now from your 3rd formula:</p> <pre><code>k(i,0) = k(i-1,i-1) + 1 </code></pre> <p>using (1) :</p> <pre><code>k(i-1,i-1) = k(i-1,0) + i-1 </code></pre> <p>then </p> <pre><code>k(i,0) = k(i-1,0) + i </code></pre> <p>then since k(0,0) = 0</p> <pre><code>k(i,0) = sum(p for p=0 to i) = i*(i+1)/2 (2) </code></pre> <p>then </p> <pre><code>(1) &amp; (2) =&gt; k(i,j) = i*(i+1)/2 + j </code></pre>