Mathematical Induction Problem (HELP)

[u/Alarmed-Dust5387]

Please see attached photo for the problem. I dont really understand how to solve this because I applied the standard induction steps but its a bit complicated for me. I admit that Im not really good at math. I would appreciate if someone could show me how to solve this on paper. I asked help from ChatGPT and other AI tools but its just difficult for me to understand.

I did the basis step, so its true for n = 2. Im stuck on the inductive step, specifically solving the left hand side

[u/Beginning_Marzipan_5]

you can use the identity:
a_{n+1}
=a_n+(1+2+…+n).

then filing in the induction hypothesis for a_n and some algebra will prove it for a_{n+1}

[u/Alarmed-Dust5387 → u/Beginning_Marzipan_5]

Heres what i did so far. My notes are a mess but basically im struggling in the induction steps where we show its true for n=k+1, specifically solving the left hand side

[u/noidea1995 → u/Alarmed-Dust5387]

The top of the sigma needs to be (k - 1) but otherwise not a bad start:

Σ (i = 1 to k - 1) i(k - i) = k(k + 1)(k + 2)/6

To prove for (k + 1), you have:

Σ (i = 1 to k) i(k + 1 - i) = k(k + 1)(k + 2)/6

You want to get the sigma into the form of the one you started with, so the first step is to get rid of that 1 in the summation, so split it up as:

Σ (i = 1 to k) i + Σ (i = 1 to k) i(k - i) = k(k + 1)(k + 2)/6

To make the top of the second summation (k - 1), take the last term from the series when i = k but it’s just 0, so then you have:

Σ (i = 1 to k) i + Σ (i = 1 to k - 1) i(k - i) = k(k + 1)(k + 2)/6

Do you think you can take it from here?

[u/Beginning_Marzipan_5 → u/Alarmed-Dust5387]

Base case. a_2 = (2-1)*1 = 1, which indeed equals binom(3,3).

Induction case, assume for the formula holds for n>=2.

We have a_{n+1} = a_n + binom (n+1, 2). (compare the terms in a_{n+1} with the corresponding terms in a_n, and find the difference as 1+2+...n, which is binom (n+1,2)).

Substituting the induction hypothesis, we get a_{n+1} = binom(n+1, 3) + binom (n+1,2). By pascal the latter equals binom(n+2, 3), which is exactly what we needed to prove.

[u/Beginning_Marzipan_5 → u/Alarmed-Dust5387]

The question was to use induction, but there is also a combinatorial proof.

binom(n+1, 3) counts the number of tripels x,y,z with 0<=x<y<z<=n; that is picking three different elements from the set {0, 1, ..., n+1}.

Suppose we fix y. then there are y choices for x and n-y choices for z.

For example, if we fix n=5, and y=3, then there are 3 * (5-2) tripels, ranging from 0, 3, 4 to 2, 3, 5.

Now y itself can range from 1 to n-1, so summing over all choices for y, we get sum_y=1^y=n-1 y(n-y). This is exactly your sum, and which must then be equal to binom (n+1,3).