Habluka's Weekly Challenge #1

[Habluka]

I just came up with the idea to have a weekly thread giving some sort of mathematical challenge to test the minds of the people in the community and to prevent the loss of mental capability now that the school terms are coming to a close in many places. These will work by me posting one or two problems every week. I'm thinking that I will post one simple one, and a slightly more interesting one.

In the threads, feel free to ask questions and you will get help as long as the answers don't give the end result. To submit an answer, please send it in a pm along with something that shows that you did work. This can be anything from a picture of you working it out on paper or the source for a program that you wrote to get your answer. If the answer is correct, I will congratulate you in the next thread. Please do not give out the answer in the thread. I will have the answer to the previous week's problem(s) in each new thread if you weren't able to figure it out and want to know.

Here we go!

1. Come up with a way of finding the sum of the first n even numbers in the Fibonacci sequence. If you don't remember what this is, it is a sequence where the first two terms are 1 and after that, each term is equal to the sum of the previous two terms (1, 1, 2, 3, 5, 8, 13, ...).
   
   
2. Expand (a + b)^n given that n is a positive integer.
   

Remember to try to have fun with this and to not kill yourself over not being able to figure these out. If you have specific questions you'd like to ask me, go ahead and do so by finding me in one of the IRC channels I frequent.

I'd like to give special thanks to Bigbaddy who gave me the idea for the second problem.

Edit: I fixed a typo in the first problem that made it slightly simpler than I intended.

[Flames]

1.idk, i haven't studied that.
[gimme 10 mins]
got it::: F(0) + F(1) + F(2) + ... + F(n) = F(n+2) - 1 . [that's the best i could do :D]

2. Use the binomial theorem

[Habluka]

1.idk, i haven't studied that.
[gimme 10 mins]
got it::: F(0) + F(1) + F(2) + ... + F(n) = F(n+2) - 1 . [that's the best i could do :D]

2. Use the binomial theorem

thanks for making me realize I made a typo in the first problem, which was supposed to be finding the sum of the first n even fibonacci numbers. Also, please submit answers through PMs

[Sepehr]

Answers

These problems are as easy as pie
1 - One can easily note that the first 2 fibonacci numbers are 1 and hence are odd. The third one is 2 which is even. The 4th and the 5th ones are odd too (odd+even = odd) and the 6th one is even. So the first n even numbers in fibonacci sequence have indices divisible by 3 (numbering them with natural numbers). Hence we need to calculate this : By the definition of fibonacci numbers, we know that which means now adding both sides together we get Now one can easily prove this identity with induction over :

Using that we get which is the desired answer.

2 - This can be calculated using Binomial coefficient which is represented in Pascal's triangle

Mod edit: use PNG rather than GIF.

[Jason]

=MyS= : 1
Everyone else : 0

No offense Hab, but Sep's got all these, he's a genius :D

[Sepehr]

The LaTeX website I used removes your conversions after a short time and I didn't know it. Will fix the LaTeX asap.

Edit #1 : LaTeX is fixed by using Online LaTeX Equation Editor but it seems to be unreadable and I don't know why. It looks to be a forum problem and I kindly ask a moderator to investigate it.

Edit #2 : I put answers in spoiler so they're not visible for those who don't want to read them.

[Marti]

Answers

These problems are as easy as pie
1 - One can easily note that the first 2 fibonacci numbers are 1 and hence are odd. The third one is 2 which is even. The 4th and the 5th ones are odd too (odd+even = odd) and the 6th one is even. So the first n even numbers in fibonacci sequence have indices divisible by 3 (numbering them with natural numbers). Hence we need to calculate this : By the definition of fibonacci numbers, we know that which means now adding both sides together we get Now one can easily prove this identity with induction over :

Using that we get which is the desired answer.

2 - This can be calculated using Binomial coefficient which is represented in Pascal's triangle

asians....

(no offense intended)

[Roflcopter]

...

It's a nice solution but more work than direct calculation with Binet's formula and geometric summation and relies on tricks that won't work for generalised version of these problems. Binet's formula is easily proved with standard recurrence relation tools.

[tempest]

but it seems to be unreadable and I don't know why. It looks to be a forum problem and I kindly ask a moderator to investigate it.

Not a forum problem. You were using GIFs, which have only binary opaque/transparent values rather than a separate alpha channel. Therefore smoothing is done in color, and in this case, it was for a white background. Fixed by using PNG instead (still less than optimal readability because it's black, though).

[Vanquish]

big words

+1

[Sepehr]

@ Larry : That's a bit higher than usual level of these kind of problems but still, Binet's formula is also easily proved with induction, too.
@ tempest : Thanks for fixing it, I appreciate it :)

[paulmuaddibKA]

The answer is :
-Always 42.
-Always 1089.
-Always one of the above.
-Always wrong.

* paulmuaddibKA feels stupid...

[Habluka]

...

It's a nice solution but more work than direct calculation with Binet's formula and geometric summation and relies on tricks that won't work for generalised version of these problems. Binet's formula is easily proved with standard recurrence relation tools.

While Binet's formula is more elegant, it kind of feels wrong having an answer that utilizes it without including a proof, which will take a little more space than what Sepehr did.

[SuperSniper]

wow.. what takes you 10 min takes me 10 days

[Sepehr]

wow.. what takes you 10 min takes me 10 days

The time it takes you to solve doesn't matter as long as you continue thinking, solving and perseverance.

[paulmuaddibKA]

wow.. what takes you 10 min takes me 10 days

The time it takes you to solve doesn't matter as long as you continue thinking, solving and perseverance.

Well, it does, as, for example, the architecture where my OS is running has flaws that go beyond imagination.
* paulmuaddibKA thinks for more than 5 minutes...
* paulmuaddibKA EXPLODES

[RCJD]

I'm looking forward to Problem #2. Actually, could we just have an official problems/brain teasers thread which everyone can contribute? I have a few of my own.

And yes Marti, asians :tongue:

[Flames]

I would have gotten the correct answer if Habluka didn't make the typo :S

[Sepehr]

Actually, could we just have an official problems/brain teasers thread which everyone can contribute? I have a few of my own.

I'd appreciate it :)

[Bullpup]

[Lantry]

binomial expander in Python

[SELECT ALL] Code:

def expand(s):
    """ Input: string representation of a binomial in the form (a+b)^n
        Output: string representation of the expanded form
    """
    n = s[s.rfind('^')+1:]
    a = s[s.find('(')+1:s.find('+')]
    b = s[s.find('+')+1:s.find(')')]
    
    result = ''
    row = pascal_row(int(n))
    for i in range(int(n)+1):
        result += str(row[i]) \
                  + '(' + a + '^' + str(int(n) - i) + ')' \
                  + '(' + b + '^' + str(i) + ') + '
    
    return result + '0'


def pascal_row(row_num):
    """
        http://mail.python.org/pipermail/edu-sig/2010-January/009758.html
    """
    numer = row_num
    denom = 1
    # initialize row of Pascal's Triangle
    row = [1]
    while numer > 0:
        row.append((row[-1] * numer/denom))
        numer -= 1  # decrement numerator
        denom += 1  # increment denominator
    return row

example use:

[SELECT ALL] Code:

>>> expand('(x+y)^2')
'1(x^2)(y^0) + 2(x^1)(y^1) + 1(x^0)(y^2) + 0'

the ' + 0' at the end is simply lazy coding on my part, I might clean the whole thing up in a bit, but for now you get the 'technically correct' version.

[Habluka]

binomial expander in Python

[SELECT ALL] Code:

def expand(s):
    """ Input: string representation of a binomial in the form (a+b)^n
        Output: string representation of the expanded form
    """
    n = s[s.rfind('^')+1:]
    a = s[s.find('(')+1:s.find('+')]
    b = s[s.find('+')+1:s.find(')')]
    
    result = ''
    row = pascal_row(int(n))
    for i in range(int(n)+1):
        result += str(row[i]) \
                  + '(' + a + '^' + str(int(n) - i) + ')' \
                  + '(' + b + '^' + str(i) + ') + '
    
    return result + '0'


def pascal_row(row_num):
    """
        http://mail.python.org/pipermail/edu-sig/2010-January/009758.html
    """
    numer = row_num
    denom = 1
    # initialize row of Pascal's Triangle
    row = [1]
    while numer > 0:
        row.append((row[-1] * numer/denom))
        numer -= 1  # decrement numerator
        denom += 1  # increment denominator
    return row

example use:

[SELECT ALL] Code:

>>> expand('(x+y)^2')
'1(x^2)(y^0) + 2(x^1)(y^1) + 1(x^0)(y^2) + 0'

the ' + 0' at the end is simply lazy coding on my part, I might clean the whole thing up in a bit, but for now you get the 'technically correct' version.

While this is sort of correct, I don't really like approaching this problem in this way since it won't work if n is too big for Python to handle while there are other ways of having a solution written out that wouldn't break when n gets too big.

[Habluka]

Just so you know, there's one day left for these problems. I'll have new ones posted early Monday morning PDT.

[bballn45]

Still in Geometry.