Re: Why some recurrence relations have solutions for f(n) = n^2 while others do not?
- From: Joshua Cranmer <Pidgeot18@xxxxxxxxxxxxxxx>
- Date: Tue, 21 Apr 2009 17:08:48 -0400
countableinfinity@xxxxxxxxx wrote:
Now for some reason this solution satisfies all the remaining
equations too. What is the reason? How can I prove this?
The sum of the first N odd numbers is N^2, so you can write the recurrence relation f(n + 1) = 2n - 1 + f(n).
Can someone please explain why we have a solution for CASE 1 and not
for CASE 2?
In this case, you want to find f(2n) given f(n):
f(2n) = 4 * f(n), if f(n) = n^2. Yet the recurrence solution in this case has the multiplier 2, which no constant addition can overcome.
--
Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
.
- References:
- Why some recurrence relations have solutions for f(n) = n^2 while others do not?
- From: countableinfinity
- Why some recurrence relations have solutions for f(n) = n^2 while others do not?
- Prev by Date: markov set theory ?
- Next by Date: PROOF: 2 + 2 Not Equal 4
- Previous by thread: Why some recurrence relations have solutions for f(n) = n^2 while others do not?
- Next by thread: Traversable graphs
- Index(es):
Relevant Pages
|
