TT's Maths Thread

[TrueTears]

We have and for . Define . As per usual to find the generating function we multiply the recurrence equation by and sum over all values of n for which the recurrence is valid. The rest is just about having the fortitude to carry out the computation, which with enough experience doesn't require much thinking at all. However, I'm aware it can be difficult to do (and understand) in the beginning, so feel free to ask about any of the steps below if you're confused and I'll go through how it works.



The left hand side is just . At this point I want to interchange the order of summation (to break the inner sum's dependence on the outer sum's dummy variable).





Now I'm going to perform an index shift in the inner sum, by starting the sum at n=0, and replacing n by n+i in the summand.





And we've broken the sum into independent parts, which is what I tried to hint at as my reason for interchanging summation order. The second bracket is just , so we'll work on the first bracket. To do this we perform an index shift starting the sum at i=0 and changing i to i+1 in the summand.







And we've done the hard part. We have . Now you can solve this functional equation for . You'll get a quadratic and hence two solutions, think about which one you should select.

Oh right, very clever, thanks Madah! I can do the rest now.

[TrueTears]

Say we have then the generalised binomial theorem says we can expand this by using:



Now my question is, how do you prove this generalised binomial theorem? Combinatorially? Algebraically?

[zzdfa]

you could try proving for rational lambda first:
so let lambda=p/q and sub it in, take both sides to the power of q, and you're left with proving that which looks doable (but messy).


then once youve done that, you can probably use some sort of limiting argument to show that
if the identity holds for rational lambda then it holds for irrational lambda as well.

[TrueTears]

Hmm, I didn't actually prove it or anything I think I just rewrote it in another form and it happens to be the same.

Say we have where

Then we have

But

[kamil9876]

yeah that's the idea Newton had behind it, to extend the natural exponent case. He even experimented by deriving from this uncertain idea the expression for and then squaring and noticing that he did indeed get

I think it can be done with taylor series. Since the kth derivative of is

[TrueTears]

Right so it exists for all real powers, what about complex?

[kamil9876]

I don't know. I havn't even learnt how to multiply real numbers yet.

[TrueTears]

Finally finished the recurrence chapter in combinatorics, took a long read cause read generating functions during it hahaha. Anyways here are some cool questions for thought (some probs require generating functions).

1. For a set of integers, define to be . How many subsets of of satisfy ? What about a generalisation?

2. Find the number of subsets of that contain no two consecutive elements of .

3. Fix positive . Define a sequence of real numbers by . Find a formula for .

4. For each , we call a sequence of (s and n)s 'legal' if the parentheses match up. For example, if , the sequence (()()()) is legal, but ()())(() is not. Let denote the number of legal arrangements for the parentheses. Find a recurrence formula for .
[WHAT THE FUCK IS THIS QUESTION EVEN ON ABOUT? WHAT DOES IT EVEN MEAN AND WHAT IS IT ASKING FOR??]

[zzdfa]

'how many ways can you arrange n pairs of brackets so that they make sense'

1 pair:
)( does not make sense
() does make sense

2 pair:
)()( does not make sense
(()) makes sense
()() makes sense

find a recurrence formula for l_n


and re. the generalized binomial theorem:

But

that line is only true if lamda is a positive integer.

I don't know. I havn't even learnt how to multiply real numbers yet.

lol wut?

[kamil9876]

2.)
Let be the number of ways of doing it for a set containing first n naturals.

We can partition these subsets into the following: Those that do contain n, those that do not contain n. If we have n in our set, then we can pick any subset from {1,2,3,4...n-2} such that there are no consecutives there, there are ways of doing this. If however our set does not have n, then we can choose any subset from {1,2,3...n-1} that does not have any consecutives, there are ways of doing this. Now we have covered every possibility in a mutually exlusive way, thus we add up:



and and can be counted manually.

I'll let you think about the rest since some of them use a similair strategy.

[TrueTears]

2.)
Let be the number of ways of doing it for a set containing first n naturals.

We can partition these subsets into the following: Those that do contain n, those that do not contain n. If we have n in our set, then we can pick any subset from {1,2,3,4...n-2} such that there are no consecutives there, there are ways of doing this. If however our set does not have n, then we can choose any subset from {1,2,3...n-1} that does not have any consecutives, there are ways of doing this. Now we have covered every possibility in a mutually exlusive way, thus we add up:



and and can be counted manually.

I'll let you think about the rest since some of them use a similair strategy.

Haha clever, I'm noticing that for a lot of recurrence problems, it is simply just partitions with a bit of fiddling around?

[kamil9876]

yep. Usually you want to partition it in such a way that the each individual part is a case that can be dealt with by knowledge of the previous term in the sequence. A common example of this is using your knowledge about n-1 elements by removing an object form a set of n elements. Or simply using knowledge about n elements, and then adding an object to see what happens(probably the more common sense way). Notice that this reminds you of induction, and in fact induction goes hand in hand with this sometimes.

Another example of this method:

how many ways are there of partitioning the set {1,2,3,....2009} into (mutually exclusive) subsets such that no two elements in the same set are consecutive?

[TrueTears]

Right, so basically for Q 2 we just have the Fibonacci sequence and the answer would just be the closed form of it haha. Ofcourse the domain of n would be restricted.

[kamil9876]

1.)

don't know if there is a simpler solution but...

S satisfies the property iff all of the following are satisfied:

1.)
2.)
3.) (for m<n-1  of course)

Therefore 1 and n-1 are definitely in S. The elements 2,3,4...n-2 can be chosen in any way, as long as condition 3) is satisfied.

To gain more insight, we can represent our possible choices in a tree diagram:




Now each path represents some subset. If the path includes m, it means you have chosen m, if it includes m', it means m' is not in the set. e.g the middle path represents {1,2,4}. The construction is such that property 3) is satisfied. This particular tree shows the answer for n=6,5,4,3,2,1. Ie to find the answer for n=6, just count how many there are in the last column: 5. the answer for n=5 is how many there are in the second last column: 3. etc. and the tree can be extended infinitely. Therefore we wish to find how many there are in the (n-2)th column.

Firstly some notation: let denote the number of elements in the kth column that are dashed ' (in other words, the number of in our tree). Let denote the number of non-dashed elements in the kth column (in other words the number of in our tree).

We have the following recurrence relations:


(because there are  elements in the kth row, and each branches of to an element (k+1) (without a '))

(since only a non-dashed element can branch of to a dashed one)

now define . clearly we wish to know the sequence f(1),f(2),f(3)... etc. and the recurrences above can be used to find a recurrence for f(k). You can guess that this recurrence is fibonacci-like just from computing a few values using the tree method (i did this manually, trust me it's not that long to work out the first few couple, and you see they are fibonacci).

Now you can just manipulate the recurrences above algebraically to prove this, or you could even use linear algebra I can imagine. Maybe even generating functions.

[kamil9876]

ok I am emabarrased to say this but thinking over my argument and disliking it's complexity and length, I realised there is a simpler one . Using properties 1,2,3: we see that we can either choose n-2 or not choose n-2, hence just partition the subsets into these two sets and you're done!