I am attempting to prove by induction that the algorithm calculates the cube of a number, I can't for the life of my grasp it. I was wondering if someone could help me please. The question is:
A function is defined recurisvely:
$1^3 = 1$
$$n^3=(n-1)^3+3\cdot q(n-1)+3\cdot n-2$$ if $n>1$.
where
$q(1) = 1$
$q(n) = q(n-1)+2\cdot n-1$ for $n > 1$
Thanks.
On
Let's state the problem more clearly:
Define by recursion $q(1)=1$ and $q(n)=q(n-1)+2n-1$ for $n>1$
Prove that, for every $n>1$, $n^3=(n-1)^3+3q(n-1)+3n-2$
Note that the recursion can also be written $q(n-1)=q(n)-2n+1$.
Let's prove the identity for $n=2$: the left-hand side is $8$; the right-hand side is $$ 1^3+3q(1)+3\cdot 2-2=1+3+6-2=8 $$
The identity can also be written $$ 3q(n-1)=n^3-(n-1)^3-3n+2=n^3-n^3+3n^2-3n+1-3n+2=3n^2-6n+3 $$ that becomes $$ q(n-1)=n^2-2n+1=(n-1)^2 $$
This form makes the proof quite easy: $$ q(n)=q(n-1)+2n-1=(n-1)^2+2n-1=n^2 $$
Okay. Let's first prove that $\operatorname{sq}$ is a square function. You should be able to do this. First prove the base case. Assume its true for $n-1$. Now begin. We know that $\operatorname{sq}(n-1) = (n-1)^2 \text{ (by assumption) } = n^2 - 2n + 1$. Try replacing it in the second definition of the function $\operatorname{sq}$.
Have you proved it?
Now for the main problem. Again prove the base case. Assume its true for $n-1$. Remember, $$(n-1)^3 = n^3 - 3n^2 + 3n -1$$ So now replace it with $\operatorname{cb}$ in the second equation where you define $\operatorname{cb}$. Use the result of the previously proved function. What do you get? What does the RHS simplify too?