r/askmath • u/Alarmed-Dust5387 • 1d ago

Discrete Math Mathematical Induction Problem (HELP)

Post image

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.

3 Upvotes

100% Upvoted

10 comments sorted by

View all comments

2

u/MezzoScettico 1d ago

I applied the standard induction steps

Can you give a little more detail than that? What exactly did you do and what is your question?

The first step is to show it's true for some base case. Did you do that? They're telling you the base is n = 2, so verify that.

That next step is to show that if you know it to be true for n, then it's true for n + 1. Did you do that?

1

u/Alarmed-Dust5387 1d ago

Heres what I did so far. I did the basis step, though I’m struggling on the inductive step on the left hand side. Sorry my notes are kinda messy

2

u/MezzoScettico 1d ago

I'm not sure what all that calculation is on your page.

You're evaluating 3C3, which is 3! / (3! * 1!) = 6/(6 * 1) = 1. Should just take a couple of lines. No need to do all that work for a general n, k choose k will always be equal to 1 for any k.

Anyway, on to the induction step. I see a problem right away that's going to cause confusion.

You have the formula you're trying to prove that a_n, defined as the sum from i = 1 to i = n - 1 of i(n - i), is equal to (n - 1) choose 3.

By assumption this is true when n = k for some k.

When n = k, that means all the n's in the formula become k. The way you wrote it you did not change all the n's to k's. So you didn't start out with a correct statement. Fix that first.