Use induction to prove that holds for all
Step 1: After zero iterations of the loop, when the loop is executed first, the value 1 assigned to the both the variables i and j.
Assume is where and
Prove that is
Suppose next iteration of the loop takes place such that j is changed by adding 2 times the previous of i and 1 to the previous j, and i is changed by adding 1.
Therefore, Q is a loop invariant.
At loop termination
So the function square is correct.