Is this a good enough proof by induction?

Although the proof seems right, it is not written correctly. Mainly it seems like you assume the claim throughout (even though you don't). Following would be a better way to write it:

Assume $P(n)$ is true, that is $\sum_{i=0}^n i^2 \leq n^3.$ We want to show $\sum_{i=0}^{n+1} i^2 \leq (n+1)^3.$

Consider \begin{align*} \sum_{i=0}^{n+1} i^2 &= \sum_{i=0}^{n} i^2 + (n+1)^2\\ &\leq n^3 + (n+1)^2\hspace{1cm} \text{(by induction hypothesis)}\\ &= n^3 + n^2+2n+1\\ &\leq n^3 +3n^2+3n+1\\ &=(n+1)^3. \end{align*}

Hence $P(n+1)$ holds.


Sahiba Arora’s answer shows how to write the induction step more clearly. But besides that you also need to show the base case $P(0)$. So I would write the whole proof something like:

Proof. We work by induction on $n$.

The base case $P(0)$ states that $\sum_{i=0}^0 i^2 \leq 0^2$, i.e. $0 \leq 0$, which certainly holds.

For the induction step, assume $P(n)$ is true… [continued as in Sahiba Arora’s excellent answer].

So by induction, the given inequality holds for all natural numbers $n$.

Tags:

Induction

Proof Writing

Solution Verification

Related

$f$ is integrable on $[a, b]$ and $F(x) = \int_a^x f(t) \, dt$. If $F$ is differentiable at $x_0$ is it always true that $F'(x_0) = f(x_0)$? Maximum of $S(\sigma) =\sigma(1)\sigma(2)+\sigma(3)\sigma(4) + \cdots +\sigma(n-1)\sigma(n)$ where $\sigma \in S_n$ Does the fraction of distinct substrings in prefixes of the Thue–Morse sequence of length $2^n$ tend to $73/96$? Is there a set $A \subset [0,1]$ such that $\int_{A \times A^\text{c}} \frac{\mathrm{d} x \, \mathrm{d} y}{\lvert x - y\vert}=\infty$? Completeness of the category of enriched categories The number of pairs $(m,n)$ of coprime positive integers that divide $k$ is $d(k^2)$, where $d$ is the divisor counting function. Show that $\exists c\in (0,1)$ such that $e^{f'(c)}=f(c)+1.$ How many isosceles triangles do you need to make any polygon? Example of an algebra which is not isomorphic to its opposite Alternative definition of product topology Introductory material for jets and jet bundles Is there a coordinate-free definition of a differential operator?

Recent Posts