Algorithm for Computing square $n^2$

Question

I have the following algorithm for computing $n^2$ based on the fact that $(n-1)^2 = n^2-2n+1$, so

$$(n-1)^2 + 2(n-1)+1 = n^2 $$

Now, to prove it outputs $k^2$ at kth step, we can use mathematical induction. I did it as follows,

Basic Step : In the base case, we can see it returns $0$.

Induction Hypothesis: Assume that $square(k)$ returns $k^2$ is correct.

Question: I am trying to prove the correctness of the algorithm. I tried to calculate $square(k)$ at kth step to verify that inductive hypothesis is correct, which assumes that algorithm returns $k^2$ at kth step. So, the algorithm should sum $2n-1$ quantity in the else statement $(k)$ times, so it should be at kth step,

$$k(2k-1)$$
$$2k^2-k$$
$$2k^2-k \ne (k-1)^2 + 2(k-1)+1 $$

So it does not return $k^2$ at $k^{th}$ step. Can you please prove that it gives $k^2$ at $k^{th}$ step?

Answer 1

Sorry if I am misreading, but it seems like your question is partly about induction itself, so let me give an overview.

Suppose you want to climb up a ladder. To do this, it suffices to know:

1. you can reach the first step
2. you can go from one step to the next

If $P(n)$ is the statement "you can reach the $n$-th step," then we can rewrite this as

1. $P(1)$ is true
2. If $P(n)$ is true, then $P(n+1)$ is true.

To be clear, this is nothing fancy, and it's entirely obvious once you understand it. Since $P(1)$ implies $P(2)$ and $P(1)$ is true, $P(2)$ is true. Since $P(2)\implies P(3)$, $P(3)$ is true, etc.

In your case, $P(k)$ is the statement "$\operatorname{square}(k)=k^2$."

1. $P(0)$ is true since $\operatorname{square}(0)=0$ by definition.
2. If $P(k)$ is true, then $\operatorname{square}(k)=k^2$. Since $k+1\neq 0$, we have $$\operatorname{square}(k+1)=\operatorname{square}(k+1-1)+2(k+1)-1=\operatorname{square}(k)+2k+1=k^2+2k+1=(k+1)^2.$$ Thus $P(k+1)$ is true.