0

I have an exercise that asks me to prove that $n^3 = (n^2-n+1)+(n^2-n+3)+...+(n^2+n-3)+(n^2+n-1)$ by induction, but I got stuck: I don't know what I can do. Could you please give me some hints? Examples: $$1^3=1 \,, 2^3 = 3+5 \,, 3^3=7+9+11 \,, 4^3=13+15+17+19$$ Note: As the exercise asks me to prove the identity $1^3 + ... + n^3 = (1+2+...+n)^2$ afterwards, I kindly ask you not to use that.

Note2: I'm aware of this identity: $ 1+3+...+2k-1 = k^2$ Thanks a lot.

LuxGiammi
  • 511
  • 1
    I am confused about your series ... it goes from -n+1 to -n+3 to ... to +n-3 to +n-1 ?!? – Bram28 Aug 14 '18 at 20:35
  • @Bram28 Seems like the terms here are $n^2+k$ for $k$ ranging from $-n+1$ to $n-1$ by twos. – BallBoy Aug 14 '18 at 20:36
  • There's a straightforward way to prove this without induction: each term is $n^2+k$, with $k$ ranging from $-n+1$ to $n-1$ by twos. How many terms are there? What can you say about the $k$ parts? – BallBoy Aug 14 '18 at 20:38
  • @Y.Forman Ah, so, say, for n=4 the added terms are -3,-1,1, and 3. Got it, thanks! – Bram28 Aug 14 '18 at 20:38
  • I updated my question. By the way, the book explicitly asks for an induction proof, even though I easily found a classic one. – LuxGiammi Aug 14 '18 at 20:41
  • Which book are you using? – Shaun Aug 14 '18 at 20:51
  • @Shaun This problem is from D. E. Knuth "Fundamental Algorithms" (exercise 1.2.1-8) – LuxGiammi Aug 15 '18 at 15:14

2 Answers2

2

\begin{eqnarray*} \sum_{k=1}^{n} (n^2-n+2k-1)= ? \end{eqnarray*} Now use your second note.

Donald Splutterwit
  • 36,613
  • 2
  • 26
  • 73
1

Hint: To get from the $n$-term sum $$ (n^2-n+1) + \dots + (n^2+n-1)$$ to the $n+1$-term sum $$ ((n+1)^2-(n+1)+1) + \dots + ((n+1)^2+(n+1)-3) + ((n+1)^2+(n+1)-1)$$ we can add $(n+1)^2-n^2-1$ to each of the first $n$ terms, and then add in the last $((n+1)^2+(n+1)-1)$ term.

BallBoy
  • 14,472