How many times does the innermost loop execute:

I did the first few by hand to see if I noticed anything.Code:`for k = 1 to n`

for j = 1 to k

for i = 1 to j

#the inner loop

end for

end for

end for

Looking at Pascal's triangle I saw the numbers appear in the diagonal. Eventually I came up with the answer:

(n + 2) choose (n - 1)

But I don't know how I got there. Does this have anything to do with the Principle of Inclusion and Exclusion?