Good luck!

____

I had double major in math and physics and a minor in computer science for undergrad study.

Now I am working as a physics Ph.D. (but still very active in learning math).

I won’t say I am very smart. It’s more about experience and the courage to try, and that’s something I think you need urgent improvement on.

For instance, for this particular question, it shouldn’t be hard to evaluate the first few terms and find out that they are 1 (you do figure this out, though you are stuck at a very easy summation for quite a while. But after all you’ve done the calculation yourself and see that they are 1).

When I finished the calculation and saw the 1, 1, 1, 1 result, I know the result should simply be 1, but I wasn’t really sure how to proceed. I actually tried three things: first I tried to use some well-known formulas like Pascal’s rule and others (see this link: https://en.wikipedia.org/wiki/Pascal%27s_rule). Actually, I have used Pascal’s rule once in one of the questions you asked several weeks ago (not sure whether you remember it, but you definitely can find it if you look for the file I uploaded), but I failed after some twenty-minute try. Then I think about using mathematical induction, as induction is very powerful in proof. However, it still doesn’t work out and I wasted another 10 minutes or so. Finally, it came to me that, since the result is so simple, it could be the result of some trivial counting problem (this is about experience, I know that many formulas in combinatorics are proved in this way, so I know this is a possible way to try), and I spent another 15 minutes or so and successfully constructed this scenario. You see, I cannot get the results immediately out of a thin air. I also need to think and try and fail and try again.

You should try on simple examples and gain experience step by step, and reviewing is also very important (for example, don’t you notice that the 4-th problem you ask this time is actually the same as one of the problems you asked before? Getting four numbers add up to 17, each ranging from 1 to 6. Now think: how is it related to the 13-combination of the multiset {5a, 5b, 5c, 5d}? Does it look like a deja-vu to you? We have solved a similar problem last time.) 

You should have more confidence in yourself. Like the non-attacking rook problem last time. You actually brought about a better idea which I didn’t think out (I tried your way, but I didn’t notice that we may treat calculating the “r_n” as a problem of putting non-adjacent rooks in a single 13-by-1 stripe. That genius idea was yours). With more experience and practice and reviewing, I believe you can have a great performance in your academic career.

_______

If you think constructing this scenario is not a formal proof, you are fundamentally wrong. Actually, many important formulas in combinatorics are proved using same delicately constructed scenarios. The procedure is: you construct a counting scenario, and you solve it in one way (which is usually very easy), and then you solve it in another way, which is significantly more complicated, and since they are solving the same problem, they must be the same. By doing this, you can show a complicated formula is equal to something very simple, just like what we do in this problem.

————————

And that is also what I mean.

The things I have written down in that question is the simplest method I can think of by far. There could be a better way, but I don’t know it.

In order to prove the formula, we are constructing a scenario, in which there are two ways of counting the same thing: choose n good objects from 2n objects where there are exactly n good ones.

One way to count is the “1+1 = 2” way: there is only one way to choose, of course, because in total there are n good ones, and if you want to have n good ones, you take all of the good ones. So on the one hand, this counting problem has answer 1.

But how is it related to that extremely complicated formula we need to prove? We solve the same counting problem, but using a more complicated method (that’s what I called a show-off method). We use the inclusion-exclusion principle to calculate the total number of possible ways of choices we can make if we don’t want “bad object 1 in our choice” “bad object 2 in our choice” ,… “bad object n in our choice”.  We want to take the intersection of the complement of those events, because if that’s the case, we won’t have any bad objects in our choice, and so we solve the counting problem in this more complicated way.

Then we show explicitly that the second way of calculation will give exactly the formula the question wants us to evaluate.

Since they are the results for the same counting problem, they must be the same, so the complicated formula must be equal to 1.

Anything clear now?

______________

I don’t see a better way to prove that it is always 1, at least for now.

Constructing that scenario is the simplest way I can think of by far.

____

Non show-off way.

There are 10 apples, 5 good and 5 bad ones.

You will take 5 from the 10 apples. How many ways are there that you choose 5 good ones?

_________________________________

Yes, it is very simple to figure out how the summation is done.

I have seen the questions you posted just now. I will work on them.

______

The summation rule is n = i + j, and it tells you that i and j are nonnegative integers.

For a given n, what are the possible choices of i and j?

______________________

It says clearly that when doing the sum, both i, j are non-negative integers, so what do you think?

_____

It’s direct calculation. Put in n = 0, 1, 2, 3 and calculate.

________________

I think you are doing it correctly.

The example in the book is a 2D square, so doing mirror symmetry/ flipping is equivalent to rotation in 3D, but in problem 1, we cannot have mirror symmetry (for instance, the mirror symmetry that exchanges 1 and 3, 5 and 7, while keeping 2, 4, 6, 8 fixed) because it will have to deform the solid box. There is no way to achieve this mirror symmetry by rotations. (It’s called chirality in chemistry)

By the way, the way you draw the box makes me feel it is a cube with equal length…

______

Here is the complete version.

Feel free to ask if you are stuck somewhere. ans

PS: I cannot say for sure my calculation for problems 1-3 is correct, even though I have checked multiple times. It’s very likely to make mistakes when playing with group theory.