You are subscribed to this thread Proving conjecture for recursive function

In summary: He believes that f(n)=0 when n is odd and f(n)=1/(n+1) when n is even. He asks for guidance on how to prove this using induction, and receives an explanation on how to approach it. He realizes that the conjecture is obviously true for a base case and that the recursive relationship needs to be proven. In summary, Sam has a conjecture for a recursive proof involving a function, f(n), with initial values f(1)=0 and f(2)=1/3. He believes that f(n) equals 0 when n is odd and 1/(n+1) when
  • #1
superdog
3
0
Hi,

Homework Statement



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,

Homework Equations



anyone care to point me in the right direction?

The Attempt at a Solution



not really sure what method to use, induction?
 
Physics news on Phys.org
  • #2
Since you have two statements:
f(2n+1)= 0 and f(2n)= 1/(2n+1), why not try two separate induction proofs?
 
  • #3
HallsofIvy said:
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
 
  • #4
superdog said:
"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.
 
  • #5
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
 

1. What is a recursive function?

A recursive function is a function that calls itself within its own code. This allows the function to repeat a certain process until a stopping condition is met.

2. How do you prove a conjecture for a recursive function?

Proving a conjecture for a recursive function involves using mathematical induction to show that the conjecture holds for the base case and then using the inductive hypothesis to prove that it also holds for the next case.

3. What is the importance of proving a conjecture for a recursive function?

Proving a conjecture for a recursive function is important because it allows us to understand and analyze the behavior of the function, and ultimately make predictions about its output for different inputs.

4. Can a conjecture for a recursive function be disproven?

Yes, a conjecture for a recursive function can be disproven if a counterexample is found that does not satisfy the conjectured pattern or behavior.

5. Are there any limitations to using mathematical induction to prove a conjecture for a recursive function?

Yes, mathematical induction can only be used to prove conjectures that involve a discrete set of values, such as natural numbers. It cannot be used to prove conjectures that involve continuous functions or infinite sets of values.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
457
  • Calculus and Beyond Homework Help
Replies
6
Views
275
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
4
Views
604
  • Calculus and Beyond Homework Help
Replies
3
Views
358
  • Calculus and Beyond Homework Help
Replies
3
Views
515
  • Calculus and Beyond Homework Help
Replies
13
Views
901
  • Calculus and Beyond Homework Help
Replies
1
Views
533
  • Calculus and Beyond Homework Help
Replies
3
Views
762
  • Calculus and Beyond Homework Help
Replies
1
Views
452
Back
Top