Algorithm for Computing square $n^2$ 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?
 A: 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:

*

*you can reach the first step

*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

*

*$P(1)$ is true

*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$."

*

*$P(0)$ is true since $\operatorname{square}(0)=0$ by definition.

*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.

A: An alternative approach is to solve the recurrence $a_{k+1} = a_k + 2k+1$ with $a_0=0$ and prove that the solution is $a_k=k^2$.
The homogeneous recurrence $a_{k+1} =a_k$ solves with $a_k = A \cdot 1^k = A$ for some constant real $A$.
The particular solution then can be picked at $a_k=k^2$ and plugging it into the recurrence you get both the eqn and the initial condition, so this is the only possible answer.
