#1) the initial values of and do not matter. you just need to notice that
so to find the radius we just use the ratio test and get
so which makes the radius of convergence
1)Let . Define , and . Find the radius of convergence of .
The next two problems are for the younger kids, so give them a chance.
2)Let be a set (non-empty) of finite terms. A "partition" is breaking the set into two sets (non-empty) so that together they have the all the elements of but none of eachother. For example, let then are partitions. But are not. Say that has elements. How many different paritions are there in terms of ?
3)Given an checkerboard what is the maximum number of checkers which can be placed so that no two are adjacent. Prove your answer. "Adjacent" means either horizontally or veritcally next to eachother not diagnolly.
well ill start by proving my first assertion
Let . Then after expanding by the recursion we have
. Notice that the second term is just the reciprocal of the original limit so we solve
. We choose the positive solution because all the terms in the sequence are obviously positive and thus a negative ratio is not possible.
First we show that the sequence is bounded.
since each term in the sequence is obviously larger than the previous term.
now define and look at the ratio which is just . (easy induction proof ill leave the verification to the reader, but if this were for some competition i would include the proof ) so the sequence is monotonically decreasing.
and every bounded monotonic sequence converges.
All these three problems are my own I hope you liked them.
Maokid7 solved the first problem the trick here is to use the ratio test for evaluating radius of convergence for infinite series. The link I gave show that no matter what two possitive numbers are chosen thier ratio is the divine proportion. So the radius is .
The second problem requires the knowledge combinations formula. Rieview them!
Now for a set we can constrct a partion in the following way. For simplicity let us say and show how we can construct partitions. Let and be two partitions. So we cannot have then that would mean (empty set) which is against the rules of the problem. Similarly . However, let us focus on only. Because once we know then is completely determined. For example, if then , this is what I mean by being completely determined. So let us count the number of different ways of choosing elements for , because again once I know that we know what is. We cannot chose all the elements at once as explained above. But we can chose elements for the number of ways this can be done is . And these are:
Now let us count the number of ways choosing element for there are ways. And these are:
So in total there are ways of creating ordered partitions. What do I mean by "ordered" I mean we make a distinction between which partition is first, , and which partition is second, . The important realization is that I overcounted the unordered partitions twice. Because these play symettric roles in this problem. Thus, the answer should be divided by two to give us .
Okay, since we understand this easy example let us generalize it for large values where is the number of elements in . If you follow everything what I did you will agree that the number of ordered partitions is:
And the reason why I start with and go up to is because as I explained otherwise if we use all the elements in one partition then the remaining partition must be the empty set which we do not want. Do you realize that sum? Do you know the fabulous identity that,
Thus, the total number of ordered partitions is,
Divide this number by two to get unordered partitions which is,
The last problem is easy but I posted it to come up with an elegant proof. Hopefully you will learn from this solution. We will use the "pigeonhole principle". It says given pigeonholes and holes, if we place these pigeons into the holes there there exists at least one hole containing pigeons. Think about it, a very trivial observation, but an important one. So this is what we will do (you will see why). Give each tile in the board a number. Let the upper left one be to its right to its right and go on up to . Then is directly below and go until to the right until . So cover up the entire board with these numbers. Now define "blocks". Block is the pair of tiles. Block is the pair of tiles. And so on. So there are different blocks. Okay, I argue that if I place peices on the checkerboard then two of them must be adjancet. To see this note that we have blocks. So two of the peices end up in the same block since . This means those two pieces must be adjacent to each other. This shows is too much. Now show it is possible to have non-adjacent peices which will show is the maximum number.
Just one thing TPH... I don't know about the American and English schools, but here in SA we don't do partitions and the combinatorics formula in school. So that's a completely unknown section of mathematics for someone like me. I'll probably only do those things next year when I get to university.
But thanks for the elementary probs, they're cool
I would have to agree with TPH on this. I have found that most of the mathematics I have actually learned has been from outside the classroom even at college. If you are truly interested in something you would want to go beyond what the class covers and try to obtain a deeper understanding.
Also you tend to retain the information better if you had to go out on your own and "discover" it.