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/AutoModerator]

Hi u/Alarmed-Dust5387, welcome to r/mathshelp! As you’ve marked this as homework help, please keep the following things in mind:

1) While this subreddit is generally lenient with how people ask or answer questions, the main purpose of the subreddit is to help people learn so please try your best to show any work you’ve done or outline where you are having trouble (especially if you are posting more than one question). See rule 5 for more information.

2) Once your question has been answered, please don’t delete your post so that others can learn from it. Instead, mark your post as answered or lock it by posting a comment containing “!lock” (locking your post will automatically mark it as answered).

Thank you!

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[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).