# Mathematical induction issue

I am struggling with two examples for my homework. I'd appreciate some help. I think the weak principle of MI is enough to solve them.

Instructions are same. Prove that ...

Assume that (0) step (prove for value 1) is true, I need step (1) (induction step).

1) for $n\ge 1$ is

$1^3+2^3+\cdots+n^3=(1+2+\cdots+n)^2$

I proceeded this way, but failed.

$1^3+2^3+\cdots+(n+1)^3=1^3+2^3+\cdots+n^3+(n+1)^3=$

using inductional assume $(1+2+\cdots+n)^2+(n+1)^3$

How to proceed now? I want to prove

$(1+2+\dots+n)^2+(n+1)^3 = (1+2+\cdots+(n+1))^2$

but I don't know how. Is this good method for example like this?

2) $\sqrt {2 + \sqrt {2 + \sqrt {2 + \cdots}}} \le 2$

-
Note that the notation for the sequence in 2) is "cute" but not necessarily well-defined unless you specify the initial condition. – user7530 Oct 18 '11 at 8:36
What initial condition you meen for example? – Ondrej Janacek Oct 18 '11 at 10:52

Welcome to math.stackexchange!

You wish to prove $$(1+2+\dots+n)^2+(n+1)^3 = (1+2+\dots+(n+1))^2.$$

To get it to look similar, expand the RHS like we do this: $(a+b)^2 = a^2+2ab + b^2$.

$$( 1+ 2 + \cdots + (n+1) )^2 = (1+2+\cdots + n)^2 + 2\cdot (1+2+\cdots +n) (n+1) + (n+1)^2 .$$

Use the fact that $1+2 + 3 + \cdots + n = \frac{ n(n+1)}{2}$ so the term on the RHS simplifies to

$$(1+2+\cdots + n)^2 + n(n+1)^2 + (n+1)^2 = (1+2+\cdots + n)^2 + (n+1)^2(n+1)$$

$$= (1+2+\cdots + n)^2 + (n+1)^3$$

as required.

For the second question, yes the method of induction works well on that example, try it!

In response to Andrew's comment:

I think you would need to use that fact in most induction proofs of this statement. But you needn't view it as an advanced fact we had to bring in, it's quite simple. Indeed, write $S = 1+2+3+\cdots + (n-1) + n$ and then right underneath that line, write the sum in reverse order: $S = n + (n-1) + \cdots + 3 + 2 + 1$. So if we add these we get $2S = (n+1) + (n+1) + \cdots + (n+1) + (n+1) + (n+1)$, where there are $n$ terms on the right hand side. The result follows. Or, since you are practicing, a proof by induction works as well!

For your second issue: The important part is the idea, then you will see you don't have to do much differently for different types of questions.

Outline: i) If $P(k)$ is any statement that depends on a natural number $k$, such that $P(k)$ being true implies $P(k+1)$ is true, then if we check $P(1)$ is true, it is true for all integers. Why?

We check $P(1)$ is true manually. But this implies $P(1)$ is true, which in turn implies $P(2)$, \cdots....

These statements don't need to be equalities, they can be inequalities, or divisibility properties, or many many other things.

-
Thank you. One question. Is it possible to solve it without using the fact about sequence you used? How? For the second question, I tried, but I am confused because there is no n in equal. We solved only equals with n in a school. – Ondrej Janacek Oct 18 '11 at 11:48
@Andrew Please see my updated answer above. – Ragib Zaman Oct 18 '11 at 13:35

For the second, define $a_n$ to be the expression with $n 2$'s. So $a_1=\sqrt{2}, a_2=\sqrt{2+\sqrt{2}}$ and so on. In general, $a_{n+1}=\sqrt{2+\sqrt{a_n}}$. We have $a_1<2$ Now can you prove that if $a_n<2$, then $a_{n+1}<2?$

-
Can I prove it this way? an+1 < 2 == sqrt(2+sqrt(an)) < 2 == 2+sqrt(an) < 4 == sqrt(an) < 2 < – Ondrej Janacek Oct 18 '11 at 15:39
@Andrew: I'm not sure how to read what you wrote. The first inequality is what you want to prove and I can't parse the double equal signs. You could say as $a_n<2, a_{n+1}=\sqrt{2+\sqrt{a_n}}<\sqrt{2+2}=2$ – Ross Millikan Oct 18 '11 at 15:47
Oh sorry. I did not realized I can use latex in comments. Double equal means next step as I am proceeding with equal before first double equal mark. So question ... can I solve this issue by common method used for solving non-equals? – Ondrej Janacek Oct 18 '11 at 18:55
@Andrew: but you have to start from $a_n<2$ and get to $a_{n+1}<2$, not the other way around. – Ross Millikan Oct 18 '11 at 19:24
Oh, you are right. Still I don't have an idea how to ... – Ondrej Janacek Oct 19 '11 at 9:37