Recurrence Relations, finding f(n)

In summary, the problem asks for a value of f(n) when n is equal to 2^k and f satisfies the recurrence relation f(n) = f(n/2) + 1 with f(1) = 1. Using the formula for solving recurrence relations, we can find that f(n) = n^(log base 2) + 1. By plugging in some values, it becomes clear that f(n) is equal to the exponent of n plus 1. This can be proven by induction.
  • #1
ramenmeal
4
0

Homework Statement


Find f(n) when n = 2^k, where f satisfies the recurrence realtion f(n) = f(n/2) +1 with f(1) = 1

Homework Equations


f(n) = a*f(n/b) + c
when n = b^k, where k is a positive integer,
f(n) = C1n^(log a base b) + C2

C1 = f(1) +c/( a-1) and C2 = -c/ (a-1)

keep in mind i may be trying to use the wrong equation...

The Attempt at a Solution



a =1, b = 2, c = 1

then C1 = 1+ 1/0 and C2 = -1/0

i'm not sure what i can do from here... c1 and c2 both include undefined #'s

perhaps I'm not even approaching the problem correctly?
 
Physics news on Phys.org
  • #2
Hi,
Now I am not sure if I understood it correctly, but it seems to be much simpler:
if n = 2^k and f(n) = f(n/2) + 1
f(n) = f(2^k) = f(2^(k-1)) + 1 = ... = f(2^(k-j)) + j

Now, the answer should be obvious.
 
  • #3
I would start by calculating some values. f(20)= f(1)= 1, f(21)= f(2)= f(1)+ 1= 2, f(22)= f(4)= f(2)+ 1= 3, f(23)= f(8)= f(4)+1= 4, f(24)= f(16)= f(8)+ 1= 5. Looks obvious to me. Of course, you still have to prove that obvious "guess". Proof by induction should work.
 

1. What is a recurrence relation?

A recurrence relation is a mathematical equation that defines a sequence of elements in terms of previous elements in the sequence. It is often used to describe how a problem can be broken down into smaller subproblems.

2. How do you find the value of f(n) in a recurrence relation?

To find the value of f(n) in a recurrence relation, you can use a variety of methods such as substitution, iteration, or the master theorem. These methods involve solving for the base case and then working your way up to the desired value of n.

3. What is the difference between a linear and a non-linear recurrence relation?

A linear recurrence relation is one where the next element in the sequence is a linear combination of the previous elements. This means that the equation does not contain any powers or products of previous elements. A non-linear recurrence relation, on the other hand, can contain powers or products of previous elements.

4. Can recurrence relations be used in other fields besides mathematics?

Yes, recurrence relations can be used in a variety of fields such as computer science, physics, and biology. In computer science, they are often used in algorithms and data structures. In physics, they can be used to model natural phenomena. In biology, they can be used to describe population growth or genetic inheritance.

5. What are some common applications of recurrence relations?

Recurrence relations have many practical applications such as in finance, where they can be used to model compound interest or stock prices. They are also used in signal processing to analyze and manipulate time series data. In addition, recurrence relations are used in coding theory to correct errors in data transmission.

Similar threads

  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
482
  • Calculus and Beyond Homework Help
Replies
4
Views
589
  • Calculus and Beyond Homework Help
Replies
5
Views
536
  • Calculus and Beyond Homework Help
Replies
3
Views
495
  • Calculus and Beyond Homework Help
Replies
6
Views
224
  • Calculus and Beyond Homework Help
Replies
1
Views
546
  • Calculus and Beyond Homework Help
Replies
6
Views
677
  • Calculus and Beyond Homework Help
Replies
3
Views
314
  • Linear and Abstract Algebra
Replies
8
Views
897
Back
Top