Register to reply

You are subscribed to this thread Proving conjecture for recursive function

Share this thread:
superdog
#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
Physical constant is constant even in strong gravitational fields
Montreal VR headset team turns to crowdfunding for Totem
Researchers study vital 'on/off switches' that control when bacteria turn deadly
HallsofIvy
#2
Apr2-08, 09:26 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,691
Since you have two statements:
f(2n+1)= 0 and f(2n)= 1/(2n+1), why not try two separate induction proofs?
superdog
#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
#4
Apr2-08, 05:26 PM
Mentor
P: 15,205
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
#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