Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Math Help - Problem 37

  1. #1
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9

    Problem 37

    1)Let A,B\in \mathbb{R}^+. Define a_0=A, a_1=B and a_n = a_{n-1}+a_{n-2} \mbox{ for }n\geq 2. Find the radius of convergence of \sum_{n=0}^{\infty}a_nx^n.

    The next two problems are for the younger kids, so give them a chance.

    2)Let S 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 S but none of eachother. For example, let S=\{1,2,3,4,5\} then \{1,2,3\} \mbox{ and }\{4,5\} are partitions. But \{1,2,3,4\} \mbox{ and }\{4,5\} are not. Say that S has n elements. How many different paritions are there in terms of n?

    3)Given an 8\times 8 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2006
    From
    Florida
    Posts
    228
    #1) the initial values of a_0 and a_1 do not matter. you just need to notice that \lim_{n\to\infty}\frac{a_n}{a_{n-1}}=\phi=\frac{1+\sqrt{5}}{2}
    so to find the radius we just use the ratio test and get

    \lim_{n\to\infty}\left|\frac{x^na_n}{x^{n-1}a_{n-1}}\right|=\lim_{n\to\infty}\left|x\left(1+\frac{a  _{n-2}}{a_{n-1}}\right)\right|=|x|\left(1+\frac{1}{\phi}\right)  <1

    so |x|<\frac{1}{1+\frac{1}{\phi}} which makes the radius of convergence \frac{1}{1+\frac{1}{\phi}}=\frac{\phi}{1+\phi}
    Last edited by putnam120; September 17th 2007 at 07:48 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2006
    From
    Florida
    Posts
    228
    about number 2.
    are the partitions \{1,2,3\}\cup\{4,5\} and \{4,5\}\cup\{1,2,3\} considered to be different? this will affect the solution. i however assume that they are not.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by putnam120 View Post
    about number 2.
    are the partitions \{1,2,3\}\cup\{4,5\} and \{4,5\}\cup\{1,2,3\} considered to be different? this will affect the solution. i however assume that they are not.
    No they are not considered different maokid7, give the younger kids a chance.

    For #1 it would be nice if you can give a full proof.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2006
    From
    Florida
    Posts
    228
    well ill start by proving my first assertion \lim_{n\to\infty}\frac{a_n}{a_{n-1}}=\phi

    Let L=\lim_{n\to\infty}\frac{a_n}{a_{n-1}}. Then after expanding a_n by the recursion we have

    L=\lim_{n\to\infty}\frac{a_{n-1}+a_{n-2}}{a_{n-1}}=\lim_{n\to\infty}1+\frac{a_{n-2}}{a_{n-1}}. Notice that the second term is just the reciprocal of the original limit so we solve

    L=1+\frac1L\Longrightarrow L^2-L-1=0\Longrightarrow L=\frac{1\pm\sqrt{5}}{2}. We choose the positive solution because all the terms in the sequence are obviously positive and thus a negative ratio is not possible.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by putnam120 View Post
    well ill start by proving my first assertion \lim_{n\to\infty}\frac{a_n}{a_{n-1}}=\phi

    Let L=\lim_{n\to\infty}\frac{a_n}{a_{n-1}}. Then after expanding a_n by the recursion we have

    L=\lim_{n\to\infty}\frac{a_{n-1}+a_{n-2}}{a_{n-1}}=\lim_{n\to\infty}1+\frac{a_{n-2}}{a_{n-1}}. Notice that the second term is just the reciprocal of the original limit so we solve

    L=1+\frac1L\Longrightarrow L^2-L-1=0\Longrightarrow L=\frac{1\pm\sqrt{5}}{2}. We choose the positive solution because all the terms in the sequence are obviously positive and thus a negative ratio is not possible.
    But you are assuming the limit exists. First show that it exists.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Nov 2006
    From
    Florida
    Posts
    228
    First we show that the sequence is bounded.

    \left|\frac{a_n}{a_{n-1}}\right|\Longrightarrow 1<\left|1+\frac{a_{n-2}}{a_{n-1}}\right|<2 since each term in the sequence is obviously larger than the previous term.

    now define R_n=\frac{a_n}{a_{n-1}} and look at the ratio \frac{R_{n+1}}{R_n}=\frac{a_{n+1}a_{n-1}}{a_n^2} which is just \frac{a_n^2-1}{a_n^2}<1. (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.
    Last edited by putnam120; September 18th 2007 at 09:27 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    South Africa
    Posts
    1,630
    Thanks
    6
    Quote Originally Posted by ThePerfectHacker View Post
    3)Given an 8\times 8 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.
    That simply means that all the pieces should either be on the white squares or black squares only. Seeing as the amount of black squares is equal to the amount of white squares, then that means the maximum amount of pieces which can be placed is: \frac{1}{2} (8 \times 8) = 32 \ pieces
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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 1/\phi.
    -----
    The second problem requires the knowledge combinations formula. Rieview them!

    Now for a set S we can constrct a partion in the following way. For simplicity let us say S=\{ a,b,c \} and show how we can construct partitions. Let P_1 and P_2 be two partitions. So we cannot have P_1 = \{ a,b,c\} then that would mean P_2 = \{ \} (empty set) which is against the rules of the problem. Similarly P_2 \not = \{a,b,c\}. However, let us focus on P_1 only. Because once we know P_1 then P_2 is completely determined. For example, if P_1 = \{ a \} then P_2 = \{ b,c\}, this is what I mean by being completely determined. So let us count the number of different ways of choosing elements for P_1, because again once I know that we know what P_2 is. We cannot chose all the elements at once as explained above. But we can chose 2 elements for P_1 the number of ways this can be done is {3\choose 2} = 3. And these are:
    P_1 = \{ a , b\} \mbox{ and }P_2=\{c\}
    P_1=\{ b, c\} \mbox{ and }P_2 = \{a \}
    P_1=\{ a, c\}\mbox{ and }P_3 = \{b \}.
    Now let us count the number of ways choosing 1 element for P_1 there are {3\choose 1}=3 ways. And these are:
    P_1 = \{a\} \mbox{ and }P_2=\{b,c\}
    P_2 = \{b\} \mbox{ and }P_2 =\{a,c\}
    P_3 = \{c\} \mbox{ and }P_3 = \{a,b\}
    So in total there are {3\choose 1}+{3\choose 2} = 6 ways of creating ordered partitions. What do I mean by "ordered" I mean we make a distinction between which partition is first, P_1, and which partition is second, P_2. 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 3.

    Okay, since we understand this easy example let us generalize it for large values n where n is the number of elements in S. If you follow everything what I did you will agree that the number of ordered partitions is:
    {n\choose 1}+{n\choose 2}+...+{n\choose {n-1}}.
    And the reason why I start with 1 and go up to n-1 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,
    {n\choose 0}+{n\choose 1}+...+{n\choose n} = 2^n.
    But, {n\choose 0} = {n\choose n} = 1.
    Thus, the total number of ordered partitions is,
    {n\choose 1}+...+{n\choose {n-1}} = 2^n - 2.
    Divide this number by two to get unordered partitions which is,
    \boxed{ 2^{n-1} - 1 }.
    -----
    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 n pigeonholes and m holes, if we place these pigeons into the holes there there exists at least one hole containing 2 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 8\times 8 board a number. Let the upper left one be 1 to its right 2 to its right 3 and go on up to 8. Then 9 is directly below 1 and go until to the right until 18. So cover up the entire board with these 64 numbers. Now define "blocks". Block \#1 is the pair of 1,2 tiles. Block \#2 is the pair of 3,4 tiles. And so on. So there are 32 different blocks. Okay, I argue that if I place 33 peices on the checkerboard then two of them must be adjancet. To see this note that we have 32 blocks. So two of the peices end up in the same block since 33>32. This means those two pieces must be adjacent to each other. This shows 33 is too much. Now show it is possible to have 32 non-adjacent peices which will show 32 is the maximum number.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    South Africa
    Posts
    1,630
    Thanks
    6
    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
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by janvdl View Post
    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.
    That is a such a bad excuse. If you really like math you do it on your own. And you learn stuff by yourself not taught in school.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    South Africa
    Posts
    1,630
    Thanks
    6
    Quote Originally Posted by ThePerfectHacker View Post
    That is a such a bad excuse. If you really like math you do it on your own. And you learn stuff by yourself not taught in school.
    Look I would have studied it if i had the time... I write my finals in two weeks...

    There's no time for doing unnecessary work at this time.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Nov 2006
    From
    Florida
    Posts
    228
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    South Africa
    Posts
    1,630
    Thanks
    6
    Quote Originally Posted by putnam120 View Post
    If you are truly interested in something you would want to go beyond what the class covers and try to obtain a deeper understanding...
    I've done that with Calculus, but I DONT have the time to go deeper into anything now.

    I'm two weeks away from writing the most important exam of my life.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Search Tags


/mathhelpforum @mathhelpforum