You are subscribed to this thread Proving conjecture for recursive function


by superdog
Tags: conjecture, function, proving, recursive, subscribed
superdog
superdog is offline
#1
Apr2-08, 08:45 AM
P: 3
Hi,

1. The problem statement, all variables and given/known data

Just having some troubles with a proof i have been asked to do, (sorry for not knowing the math code)

basically, f(1)=0, f(2)=1/3 and f(n)= ((n-1)/(n+1))*f(n-2)

and i've come up with the conjecture that f(n) = 0 when n is odd, and = 1/(n+1) when n is even.

and i have to prove my conjecture, this is where i'm stuck,

2. Relevant equations

anyone care to point me in the right direction?

3. The attempt at a solution

not really sure what method to use, induction?
Phys.Org News Partner Science news on Phys.org
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city
HallsofIvy
HallsofIvy is offline
#2
Apr2-08, 09:26 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,885
Since you have two statements:
f(2n+1)= 0 and f(2n)= 1/(2n+1), why not try two separate induction proofs?
superdog
superdog is offline
#3
Apr2-08, 05:01 PM
P: 3
Quote Quote by HallsofIvy View Post
Since you have two statements:
f(2n+1)= 0 and f(2n)= 1/(2n+1), why not try two separate induction proofs?
Hey,

thanks for your help,

"f(2n)= 1/(2n+1)" you mean 1/(n+1) right, (not being picky just making sure)

yeah, i kinda what your saying, ie: 2n is a generator for all evens and 2n+1 is for odds, however, i'm not really confident on how to actually go through and do a induction proof on either, the recursive function is knda scaring me at the moment

D H
D H is online now
#4
Apr2-08, 05:26 PM
Mentor
P: 14,457

You are subscribed to this thread Proving conjecture for recursive function


Quote Quote by superdog View Post
"f(2n)= 1/(2n+1)" you mean 1/(n+1) right, (not being picky just making sure)
Halls meant exactly what he said: [itex]f(2n)=1/(2n+1)[/itex]. You conjecture is that when n is even, [itex]f(n)=1/(n+1)[/itex]. Another way of saying n is even is saying that [itex]n=2m[/itex], where [itex]m[/itex] is an integer. Apply this to your conjecture: [itex]f(n)=1/(n+1)\;\rightarrow\; f(2m) = 1/(2m+1)[/itex].

To prove some conjecture by induction, you need to show two things:
  • That the conjecture is true for some base case and
  • That if the conjecture is true for some m then it is also true for m+1.

The conjecture is obviously true for [itex]m=1[/itex] as [itex]f(2\cdot1) = 1/(2\cdot1+1) = 1/3[/itex]. All that remains is proving the recursive relationship.
superdog
superdog is offline
#5
Apr2-08, 05:31 PM
P: 3
Ahhhh, ok, thanks so much for the help! its all clicking into place now. especially after walking away from the bloody thing for a bit :P

thanks again
Sam


Register to reply

Related Discussions
No notification on a subscribed thread (and it's only the 1st post after mine) Forum Feedback & Announcements 7
even summation with recursive function in c++ Programming & Computer Science 1
proving limits of recursive sequences using definition Calculus & Beyond Homework 5
Recursive Function Computing & Technology 4