Recurrence Definition and 239 Threads

Homework Statement Solve and prove your solution for the following recurrence relation for the number of comparisons in Binary Search: C(21 - 1)=1 C(2i - 1) = 2 + C(2(i+1) - 1) The Attempt at a Solution The setup for this would be: C(n)=[SIZE="7"]{ 1, n=1 and 2 + C(2(i+1) - 1), otherwise...

Homework Statement 2xy" + y' + xy =0 xo=0 find the indicial equation, recurrence relation and series solution. Homework Equations The Attempt at a Solution I've done most of the work but i don't know how to use a recurrence relation to obtain a y1 and y2 series solution...

Homework Statement Find the recurrence relation to 1,1,2,5,12,47,...The Attempt at a Solution Made all sorts of attempts. I'm not experienced with these things. Was there a site that works these things out for you?

How do you find a recurrence relation from a given problem?

1. solve the following recurrence relation for a[SIZE="1"]n 2. (n+2)a[SIZE="1"]n+1= 2(n+1)a[SIZE="1"]n+2^{n}, n>=0, a[SIZE="1"]0=1 I shifted the index, multiplied through by the 2^{n} term and then subtracted the resulting equation from the original equation to get rid of the 2^{n}...

Hello, I was hoping someone could help point me in the right direction. I am trying to figure out how to solve recurrence relations using Mathematica (6). I have tried to search the web for information on how to use the recurrence relation solving package but I must be doing something wrong...

Homework Statement I(subscript n)=integral (from pi/2 to 0) [sin(x)]^n * [cos(x)]^2. Show that I (subscript n) = [(n-1)/(n+2)] I(subscript (n-2)) I think ur meant to use integration by parts on it somewhere but i don't know wat to use it on.

Hi, I'm trying to solve this recurrence equation. Homework Statement Solve y[k+2]+y[k]=sin(k). The answer is already given, it's y[k]=c_1sin(\frac{\pi}{2}k) + c_2cos(\frac{\pi}{2}k) + \frac{sin(k)+sin(k-2)}{2(1+cos(2))} Homework Equations The Attempt at a Solution First I solve...

[SOLVED] Recurrence Relations Homework Statement I need to express this recursive statement as a nonrecursive formula, using the technique of itteration. a_n = (n+1)a_{n-1} a_0 = 2 The Attempt at a Solution a_n = (n+1)a_{n-1} a_n = (n+1)(n+1)a_{n-2} = (n+1)^{2}a_{n-2} a_n =...

Homework Statement Find and prove the recurrence relation for the Fibonacci cubed sequence. Homework Equations By observation (blankly staring at the sequence for an hour) I've decided that the recurrence relation is G_{n} = 3G_{n-1} + 6G_{n-2} - 3G_{n-3} - G_{n-4} (where G is Fibonacci...

Homework Statement Solve the following for a_n in terms of x: a_{n+1} = \sqrt{x + a_n} Homework Equations The Attempt at a Solution Besides getting rid of the radical, I have no idea how to solve this.

Homework Statement We were asked in a class discussion if we could try to figure out the recurrence relation of the Fibonacci squared sequence. I correctly figured that the equation was F^{2}_{n}=2F^{2}_{n-1} + 2F^{2}_{n-2} - F^{2}_{n-3} with F^{2}_{1} = 0 and F^{2}_{2} = 1 and F^{2}_{3}...

Hello, I hope I have posted this in the correct place, if not, sorry. Okay, I have just started working through the material, but I am having some problems working out one of the examples, which is given below: U[SIZE="1"]n+2 = 12U[SIZE="1"]n+1 - 20U[SIZE="1"]n (n = 0,1,2...) We are...

Homework Statement In the first solution to 1999 A3 at the this website: http://www.unl.edu/amc/a-activities/a7-problems/putnam/-pdf/1999s.pdf You do not need to read the problem. I do not see hot they go the recurrence relation in the first sentence. Specifically I do not follow reason why...

How would you go on proving the following conjecture? Given S_0 = 0, \quad S_1 = 1, \quad S_n = a S_{n-1} + b S_{n-2} Prove that { S_n }^2 - S_{n-1} S_{n+1} = (-b)^{n-1} \quad (n = 1, 2, 3, ...)

Hey, I came across this recurrence relation and was wondering if there was a closed-form solution for it. a_n = \sqrt{2 + a_{n-1}}, a_0 = \sqrt{3} Assuming n \in \mathbb{N}, of course. I know that's it's possible to solve homogenous and inhomogenous recurrence relations using certain...

Hi, I would like to tell the room I’m a novice. I know very little math, mostly Algebra. So asking these questions in themselves are over my head. But I have a question that I wonder can be shown mathematically. I want to know if there can be an infinite recurrence. (For all I know it could...

Fundamental group of RP^n by recurrence!? Homework Statement That's it. Find the fundamental group of RP^n by recurrence. The Attempt at a Solution It's just obvious to me that it's Z/2 no matter n but what is this recurrence argument that I'm supposed to use?

hello any one can help me with this question thanx (a) Find a recurrence relation for the number of n-digit sequences over the alphabet {0, 1, 2, 3, 4} with at least one 1 and the first 1 occurring before the first 0 (possibly no 0’s). (b) What are the initial conditions? (c)...

hello please check my answer and let me know if there are any errors and if there are better ways to solve ... Solve the recurrence relation an = an−1 + 20an−2 with a0 = −1 and a1 = 13. Step – I : Find Characteristic equation and solve for its roots: an = an−1 +...

Can anyone point me to resources showing me how to prove recurance equations like: I(n) \le c if n = 0 d+I(n-1) if n >= 1 i.e. I(n) \le c + dn Also for proving things like: 30000n^2 + n \log n is O(n^3) using the basic definition of big-O notation (f(n) \le k \cdot g(n) for some...

Homework Statement Here's my problem - Give the order of linear homogeneous recurrence relations with constant coefficients for: An = 2na(n-1) The Attempt at a Solution I have no idea on how to start this problem - Any help would be greatly appreciated.

Does anyone know of an accessible reference that sketches a proof of Poincare's recurrence theorem? (This is not a homework question.) I'm coming up short in my searches -- either the proof is too sketchy, or it is inaccessible to me (little background in maths, but enough to talk about...

Question: "Find a recurrence relation and initial conditions for the sequence {a sub n} if a sub n is the number of bit strings of length n that contain three consecutive 0's." So here's what I have so far... n > 3 n = 4, 1000, 0001 n = 5, 10000, 00001, 00010, 01000, 10001 n = 6...

ello ello! I ran into this problem and i went in circles trying to figure it out. Anyone have any suggestions? Here is what i have: Find the solution to the following lhcc recurrence: http://cwcsrv11.cwc.psu.edu/webwork2_files/tmp/equations/3c/1e4624e0fc726276872050e3ffe28d1.png with...

Hello. I've searched around a bit for a math forum where I could get help with this and this seems like the one I found where I could get some help with this. I was posed the following problem. Now I must admit it is over my head (as is most of the math on this forum) I was hoping that...

How do we actually solve the Recurrence relation...is there any procedure... Suppose i want to solve: t(m,n) = n.t(m-1,n) + t(m-1,n-1) where t(1,*) = t(*,1) = 1. How to do it?

I am at a loss on how to get the correct answer to this question. How many comparisons are needed for a binary search in a set of 64 elements? I know the formula f(n) = f(n/2) + 2 I know the correct answer which is 14. No matter what I do I cannot come up with this answer...

Here is the famous thing, sum of k from 1 to n is n*(n+1)/2. I'm trying to show this by recurrence equation. Then an is the sum, I have this equation: an=a(n-1)+n. It's not a*(n-1), just like this kind equations n indicates the number of the term. The charcteristic equation is r^2-r-n=0...

Ok I'm giving these another go. I found the following DE from a reduction of order problem and figured that it would be an alright question if I turned it into one requiring a series solution. However I'm stuck. I think it's just a matter of index shifts to get an appropriate recurrence relation...

Hi, It has been a long time, and I do not remember how to set up a probability calculation with the following variables - take a lottery that draws 12 numbers, values 0-9 only, from a hopper that replaces the number after it is drawn, i.e. probability of each number appearing remains...

Poincare Recurrence Theorem states that: "If a flow preserves volume and has only bounded orbits then for each open set there exist orbits that intersect the set infinitely often." But it does not imply (does it?) that "In hamiltonian system with bounded phase space, all trajectories will...

Consider the recurrence x_k+2 = ax_k+1 + bx_k + c where c may not be zero. If a + b is not equal to 1 show that p can be found such that, if we set y_k = x_k + p, then y_k+2 = ay_k+1 + by_k. [Hence, the sequence x_k can be found provided y_k can be found] First of all, sorry about the...

For our combinatorics class there is a bonus excercise in which we have to solve the following recurrence relation: L_k(x) = L_{k-1}(x) + xL_{k-2}(x) My first thought was to construct the following generating function: F(x,y) = \sum_{k=0}^{\infty} L_k(x) y^k. By putting in the...

A set of blocks contains blocks of heights 1, 2, and 4 inches. Imagine constructing towers of piling block of different heights directly on top of one another. Let t(n) be the number of ways to construct a tower of height n inches. Find a recurrence relation for t(1), t(2), t(3)... Here's...

Hi... 1. so can i say that a recurrence relation is a description of the operation(s) involved in a sequence...?... 2. is the formula for an arithmetic sequence, a recurrence relation...?... and is the formula for a geometric sequence, a recurrence relation...?...

I need to show that the solution of a_n = c_1a_{n-1} + c_2a_{n-2} + f(n) (1) is of the form U_n = V_n + g(n) (2) where V_n is the solution of a 2. order linear homogenous recurrence relation with constant coefficients. Could I use the argument that if (2) is a solution...

Lectori salutem. Can anyone refute the finite space/energy/matter in infinite time theory? Finite space/energy/matter implies that the universe is not something endlessly extended, but set in a definite space as a definite force. Infinite time implies that it has never begun to become...

Lectori salutem. This seems like a cosmological question, so I will put it here: Can anyone refute the finite space/energy/matter in infinite time theory? Thanks in advance. Sauw