Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The sequence is described by $x_{n+1}=x_{n} + (n+1)^3$. Prove that $x_{n} = (n^{2}(n+1)^{2})/4$ via complete induction. I actually have two questions.

  1. I'm a bit lost as to how to start the induction and what should be step, could someone please provide some assistance? I just want a line of thought, I would like to try to solve it, so please don't solve it for me. :)

  2. I was able to prove it via "normal math", by reducing $x_{n+1}=x_{n} + (n+1)^3$ to $x_{n}=x_{n-1} + n^3$ and then replacing $x_{n-1}$ with the equation $x_{n-1} = ((n-1)^{2} n^{2})/4$.

Then I did: $(n^{2}(n+1)^{2})/4 = ((n-1)^{2} n^{2})/4 + n^3$

I then got $0=0$, which proves it's valid, right?

Thanks a lot guys!

share|improve this question
    
Why did your teacher ask you to prove this using strong induction? It's a perfect candidate for ordinary induction and I don't see a way to take advantage of the strong inductive hypothesis in a nontrivial way... –  user7530 Nov 1 '11 at 17:23
    
The start is a bit of a puzzle. You absolutely should also have been told what the "first" $x$ is. So you should have been told either that $x_0=0$ or that $x_1=1$. Without that "initial condition" kind of information, you cannot prove that the desired formula holds. Your procedure is basically correct. There is no need to change subscripts. If you don't, you need to show that $n^2(n+1)^2/4 +(n+1)^3=(n+1)^2(n+2)^2/4$, which is not really harder. I shudder a bit at the $0=0$ stuff. Just manipulate one expression or the other or both and show you get the same thing. –  André Nicolas Nov 1 '11 at 17:26
    
@user7530, I question myself the same. I still don't know how to proove it using strong induction though. –  Clash Nov 1 '11 at 21:15
    
@André Nicolas, sorry, $x_0=0$ –  Clash Nov 1 '11 at 21:15

1 Answer 1

up vote 2 down vote accepted

Technically, you don't need to 'start' a complete/strong induction. You simply prove that if the result is true for all $k\lt n$, then the result is true for $n$. If the argument works for every value of $n$, you are done (no basis of induction needed); see my comments here. However, it is often the case that the argument does not work for all values of $n$ (especially small ones), and so "special cases" have to be proven explicitly.

So: we assume that for every $k\lt n$ we know that $x_k = (k^2(k+1)^2)/4$. We want to prove that $x_n = (n^2(n+1)^2)/4$.

Since $x_n = x_{n-1} + n^3$ (provided $n\gt 0$... see below), we have: $$\begin{align*} x_n &= x_{n-1} + n^3\\ &= \frac{(n-1)^2n^2}{4} + n^3 &\text{(induction hypothesis)}\\ &= n^2\left(\frac{(n-1)^2}{4} + n\right)\\ &\vdots \end{align*}$$ and you should keep working to see if you can show that $x_n$ is indeed equal to $(n^2(n+1)^2)/4$.

However, the argument only works if $n\gt 0$; otherwise, there is no "$x_{n-1}$."

That means we would need to do the case $x_0$ directly. That is, we need to establish the Special case $n=1$.

However, you have no definition for $x_1$! That makes it pretty hard to prove.

So what we have here is that the formula is true for all $n$ if $x_1 = \frac{1^2(2)^2}{4} = 1$, because then the entire inductive argument will be valid. But if $x_1\neq 1$, then the formula does not hold for all $n$ (it fails already for $n=1$). Absent a definition of $x_1$, we don't know which one.

You note below that you know that $x_0=0$. So we just verify that the formula works for $n=0$ and we are done.

(In fact, this problem is "really" solved by ordinary mathematical induction rather than strong induction; not much of a problem).


As to your attempt: generally it is a bad idea to start with the equality you want to prove, manipulate it, and end up with something like "$0=0$". Because you can start with something false and end up with something true. For example, if you start with $1=-1$, you can then square both sides to get $1=1$; the latter is true, the former is not. So before you conclude that your original equality is true, you need to go through every step you took in the reverse order to verify that they are all "reversible". That is, you need to start with your $0=0$, and see if you can work back up to the equality you want.

That's why it is generally better to start with one side of the equation, and see if you can manipulate it until you get the other side in order to establish equality.

share|improve this answer
    
sorry! I completely forgot to add that $x_0=0$! But thanks for the great and fast answer! –  Clash Nov 1 '11 at 17:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.