Trying to prove this equality involving a summation of a binomial coefficient.

[jdinatale]

I immediately thought of induction, so that is what I used, but I can't seem to make any progress past a certain point.

 

[tiny-tim]

hi jdinatale!

(i haven't looked at your induction proof , but …)

why not just multiply the LHS by n+1 ?

 

[jdinatale]

hi jdinatale!

(i haven't looked at your induction proof , but …)

why not just multiply the LHS by n+1 ?

Ok, I tried that and I eventually could not go any further. Any ideas on what's going wrong?

 

[tiny-tim]

hi jdinatale!

in the third line you have ∑_k=0…j ^j+1C_k+1

put m = k+1, that's ∑_m=1…j+1 ^j+1C_m …

what is that? ​

 

[jdinatale]

hi jdinatale!

in the third line you have ∑_k=0…j ^j+1C_k+1

put m = k+1, that's ∑_m=1…j+1 ^j+1C_m …

what is that? ​

Brilliant! I've solved the problem now, thank you so much. But please tell me, how did you possibly know to do that? That was not obvious to me at all, and I'm not sure how you would just know to do that.

 

[tiny-tim]

easy!

the clue was in the question …

the RHS said 2ⁿ⁺¹,

which i know is ∑ ⁿ⁺¹C_r ​