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.

[Sarath]

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]

(21 May 12 08:45AM)Sarath Wrote:  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 (Click to View)

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]

(21 May 12 10:00AM)Sepehr Wrote:  

Answers (Click to View)

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]

(21 May 12 10:00AM)Sepehr Wrote:  ...

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]

(21 May 12 11:28AM)Sepehr Wrote:  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).

[Vanqu!sh]

(21 May 12 02:04PM)Roflcopter Wrote:  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]

(21 May 12 02:04PM)Roflcopter Wrote:  

(21 May 12 10:00AM)Sepehr Wrote:  ...

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]

(21 May 12 10:32PM)SuperSniper Wrote:  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]

(Yesterday 09:47AM)Sepehr Wrote:  

(21 May 12 10:32PM)SuperSniper Wrote:  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:

[Sarath]

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

[Sepehr]

(Today 04:49AM)RCJD Wrote:  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 :)