Recurrence Definition and 239 Threads

Hi all, I came across a linear recurrence with polynomial coefficients and realized that I don't have a clue as to how to solve it. The usual methods like generating functions or guessing seem not to work in that case. Here is the equation: i (i - 1) (i - 2) b[i] = 1/3 (i + 1) i (1 -...

Homework Statement Let T_{n} denote the number of different partitions of {1,2,...,n}. Thus, T_{1} = 1 (the only partition being {1}) and T_{2} = 2 (the only partitions being {1,2} and {1},{2}). show that T_{n+1} = 1 + \sum^{n}_{k=1} (^{n}_{k}) T_{k}. Homework Equations Let S be a given...

Homework Statement a_n+3a_{n-1}-10a_{n-2}=2^n The Attempt at a Solution I missed the lectures that addressed how to solve these kinds of problems, and while studying my recommended textbook it only went as far as solving recurrence relations that are equal to 0 as opposed to 2n. I...

_nx represents the nth iteration. Homework Statement Show that {_{n+2}}x = _nx + M^{-1}(b-A{_nx}) Homework Equations {_{n+1}}x = _nx + M_1^{-1}(b-A{_nx}) {_{n+2}}x = {_{n+1}}x + M_2^{-1}(b-A{_{n+1}x}) M = M_1(M_1+M_2-A)^{-1}M_2 The Attempt at a Solution I tried was...

Hello, I am trying to solve a Pell's equation X2 + 2Y2 =1 I understand that the (3,2) is a fundamental solution to the equation. However, I am having difficulty to obtain the recurrence formula in order to generate further solutions. Can anybody help?

Homework Statement Let a0, a1, a2..., be defined by the formula an = 3n + 1, for all integers n >= 0. Show that this sequence satisfies the recurrence relation ak = ak-1 + 3, for all integers k >=1. Homework Equations for all integers n >= 0, an = 3n + 1 for all integers k...

The alpha beta filter equation is given by this Xni = AXn + BXn-1 Xn-1 is subscript i want to figure the solution to this recurrence relation, but is it a recurrence relation? i am wondering weather alpha beta filters grow faster than exponential smoothing filters.- i said it is a 1st order...

Homework Statement [PLAIN]http://img812.imageshack.us/img812/5261/unleduqi.png Homework Equations The Attempt at a Solution Can anyone help with part (a)ii, is pk=(1/2)^k? I can't see how to find qk

Homework Statement I am doing a power series solution for: (x^2-1)y" + 8xy' + 12y = 0 I rewrote it in terms of power series and transformed everything into one series and finally ended up with the following recurrence relation: an+2= ((n+3)(n+4)an)/((n+2)(n+1)) I plugged in values for n...

I am totally new to this area, and have some major trouble understanding how recurrence relations were derived from the problems, what to do and what's not. Really appreciate any guidance!For example: Give a Ternary String (containing only 0s, 1s, or 2s), we have to find out the recurrence...

Homework Statement I need to find an expression for: y^{2}H(y) I know how to find: yH(y) with: yH(y)=\frac{1}{2}H_{n+1}(y)+nH_{n-1}(y) I looked through the miscellaneous relations but nothing stuck out to me. Can someone give me some guidance on how to go about finding a relation...

Dear forum people, for a nonlinear software I am writing I am having a hard time to transform a recurrence relation to an explicit function. Maybe someone can help me along the right lines... The recurrence relation is of the form (an exponential type function) y[n+1] = y[n] + k *...

Homework Statement See figure attached, we are asked to use power series to solve the differential equation. Homework Equations The Attempt at a Solution I'm confused as to how to deal with the -1 in the indices of one of my summations. I could add the term on the outside and...

reading the very interesting discussion on the long thread on the 2nd law, had a couple of much more basic questions regarding entropy & the Poincaré Recurrence Theorem A) is the reduction of entropy implied by the theorem a real, unresolved paradox in physics? B) if you take a...

1. I am trying to practice solving recurrence relations but get stuck when it comes to generalizing the last part of them and would be grateful if someone could offer some help. I'm not very good with series which is why I may be having some problems with them. Here are a few examples if its...

\textup{A 2 x 7 rectangle has tiling with 1 x 1 and 1 x 2 tiles (singletons and doubletons).} \textup{How many such tilings of a 2 x 7 grid are there?} \textup{Let }a_{n}\textup{ be the number of tilings of a 2 x n grid using 1 x 1 and 1 x 2 tiles so that the} \textup{two rightmost squares...

Consider a 2D variable coefficient linear recurrence relation. An example might be: b_{n,j+1} (j+1)(2n-1)(2n-2) = (2n-2+j)(2n-1+j)b_{n-1,j} which has the solution b_{n,j} = \frac{(2n-1+j)!}{(2n-1)!j!} Is there any algorithm that can be used to derive this result? I have a recurrence...

Homework Statement I'm solving the quantum harmonic oscillator. And I'm solving Schrodinger equation. So I came up to one part where I have to use power series method of solving DE (that or Frobenius would probably work just fine). Now I have the recurrence relation...

Homework Statement [PLAIN]http://img530.imageshack.us/img530/6672/linn.jpg The Attempt at a Solution For parts (a) and (b) I've found the eigenvalues to be -\frac{1}{3} and -1 with corresponding eigenvectors \begin{bmatrix} -1 \\ 3 \end{bmatrix} and \begin{bmatrix} -1 \\ 1...

Homework Statement An+2=6An+1+6An A1=A2=1 Bn+2=5Bn+1+9Bn B1=B2=10100 a) is it true that Bn>An for every integer n > 0? b) is it true that Bn>An for infinetly many integers n>0? The Attempt at a Solution It just seems like these are increasing functions since they both start with...

If you are given a sequence of integers such as: An=xn+yn where x and y are integers. and n=0,1,2,3... how would one find the recurrence relation? I tried writing An+1 in terms of An but it doesn't come out neatly because it doesn't translate so well. And there are terms raised to the n+1...

I know how to solve second order ones, but how would you solve third order ones? Because the characteristic polynomial would have a third degree so how can one find the roots? I have looked everywhere online to find out but I can't find anything. Please Please tell me!

Homework Statement An=3An-2-2An-3 When A0=3 A1=1 A2=8 I tried to solve it normally like a normal recurrence relation however since it is not A sub n-1, it turns into a polynomial where the variable is raised to the third power which I couldn't factor and the whole thing turned into a mess.

So I was reading up about the derangement recurrence relation proven in a combinatorical way. The proof I was looking at is at this webpage. The combinatorical proof is at the bottom of the page below the algebraic proofs. [PLAIN]"ttp://planetmath.org/?op=getobj&from=objects&id=11991"[/URL]...

Homework Statement Solve the Mass-Spring-Damper Differential equation mx''+bx'+kx=exp(-t)cos(t) (Where x'' is d2x/dt2 etc, don't know how to do the dots above :confused:) I understand how to solve this problem, but the thing that confuses me is that the right is in terms of "t"...

Hello; I do not have any experience in solving non-linear recurrence relations, so I was just wondering how one solves them. For example, consider the sequence: 1, 2, 6, 15, 31, 56 In general, F_{n+1} = F_{n} + n^{2} Do I still substitute F_{n} = k^{n}? Thanks.

Homework Statement Suppose that a mathematical expression can only be formed by the following symbols: 0, 1, 2, …, 9, ×, +, /. Some examples are “0 + 9”; “2 + 2 × 8”; “1 / 5 + 6”. Let an be the the number of such mathematical expression of length n (e.g. “0 + 9” is considered of length 3)...

Homework Statement find a logical expression using only ∧ and ¬ operators which is logically equivalent to (p ∨ q) The Attempt at a Solution losing direction what should I first consider? There is another question about recurrent relation. Suppose that a mathematical expression can...

Homework Statement Let's say I had this recurrence relation: log\left(f\left(x+2\right)\right) = log\left(f\left(x+1\right)\right) + log\left(f\left(x\right)\right) How do I prove, then, that... f\left(x\right) = e^{c_1 L_x + c_2 F_x} ? Homework Equations There probably are...

[PLAIN]http://dl.dropbox.com/u/471735/Recurrence.png

How to solve recurrence relation with one real root and two complex roots ? The Example is ; Solve the recurrence relation a n-1 + a n-3 = 0 where n ≥ 3 and a 1 = 1 a 2 = 1 a 3 = 2 a n = nth order a n-1 = (n-1)th order. a n-3 = (n-3)th order. I've started the solving ; a n = r^n so...

Any suggestions on how to approach solving: \Psi(m,n) \leq \Psi\left(\left \lfloor\frac{m}{2}\right\rfloor,n_1\right) + \Psi\left(\left \lceil\frac{m}{2}\right\rceil,n_2\right) + 16n^*+11m \lceil\text{log }m\rceil where n = n_1 + n_2 + n^*

I'm really puzzled about this one. Say you have a discrete, nonnegative random variable N where the probability pn = P{N=n} satisfies the recurrence relation p_{n+2} + r p_{n+1} + s p_n = 0 for n = 0, 1, 2, ...; p0 and p1 are given. How do you find the expectation E[N] without solving...

Homework Statement The sequence f_n is defined by f_0=1, f_1=2 and f_n=-2f_{n-1}+15f_{n-2} when n \geq 2. Let F(x)= \sum_{n \geq 2}f_nx^n be the generating function for the sequence f_0,f_1,...,f_n,... Find polynomials P(x) and Q(x) such that F(x)=\frac{P(x)}{Q(x)} The Attempt at a...

Homework Statement The sequence f_n is defined by f_0=f_1=2 and f_n = (\frac{f_{n-1}+2f_{n-2}}{6}), when n\geq2. Find a non-recursive formula for f_n The Attempt at a Solution Well I have solved for the closed formula of the generating function which I will call g(x) so...

Homework Statement Solve the recurrence system below and dtermine a formula for the time complexity function T(n). T(0) = 4. T(n) = 5 + T(n - 1) (n > 0) The Attempt at a Solution T(3) = 5 + T(2). T(2) = 5 + T(1). T(1) = 5 + T(0). T(3) + T(2) + T(1) = 3 * 5 + T(2) + T(1) + T(0)...

How to solve recurrence relation ? The Example is ; Solve the recurrence relation a n + 2a n-1 + 2a n-2 = 0 where n ≥ 2 and a 0 = 1 a 1 = 3 a n = nth order a n-1 = (n-1)th order. a n-2 = (n-2)th order. I've started the solving ; a n = r^n so the equation will be ; r^n + 2r^(n-1)...

Homework Statement Homework Equations We're using generating functions, and recurrence relations of homogeneous and non-homogeneous types The mark allocation is 2, 3, 3 and 2 The Attempt at a Solution I think I've done the first part correctly. The closed form is in terms...

Homework Statement Solve the recurrence relation an = 5an−1 − 3an−2 − 9an−3 for n ≥ 3 with initial values a0 = 0, a1 = 11, and a2 = 34. Homework Equations its given lol The Attempt at a Solution I found that the characteristic equation for this rr is x3 - 5x2 + 3x + 9 and found...

Homework Statement T(n)=b n<=2 8T(n/2)+e(n^(2)) n>2 Homework Equations The Attempt at a Solution O((n^log)2^(7))

Is it possible to find a recurrence relation of tan(nx) where n is a positive integer and x is a real variable? My friend said that it is possible. I don't see how to do it. Does anyone have a way to do it?

Prove the following recurrence by induction T(n) = 2T(n/2) + n lg n = Θ ( n lg^2 n ), T(1) = 1 This to me looks scary and I was wondering if anybody had a heads up on how to solve for this

Hello: I am asked to find a recurrence relation for the number of n letter sequences composed of A, B, C where every A that is not in the last position is followed by a B. So, would this be: A| (we have A(n-2) sequences) + 0 if A is in the last position B| we have A(n-1) C| we have...

Homework Statement In the following series': http://image.cramster.com/answer-board/image/cramster-equation-2009410014306337491927047975008434.gif According to my book, we only have a common range of summation here for n >= 2. Therefore we need to treat n = 0 and n = 1 separately...

Homework Statement Box A contains three white balls and one red ball while box B contains four white balls. One ball is randomly drawn from each box and the two balls are then randomly put back into the boxes so that each box still contains four balls. This process is performed n times. Let...

Is there a general method for solving 2-index recurrence relations with constant coefficients? Here is one I would like to solve a_{m,n} = \frac{xa_{m-1,n} + ya_{m,n-1} + 1}{x+y} for m,n > 0 with initial conditions a_{m,0} = m/x and a_{0,n} = n/y. Hoping for an analogy with...

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 am currently studying the Mandelbrot set, and have a question about one of the statements on http://mathworld.wolfram.com/QuadraticMap.html" . It says the recurrence for the Mandelbrot set "is not in general solvable in closed form." What does this mean?

Homework Statement A sequence of terms U_{k} is defined by K \geq by the recurrence relation U_{k+2} = U_{k+1} - pU_{k} where P is a constant Given that U_{1} =2 and U_{2} = 4 a) find an expression in terms of p for U_{3} b) hence find an expression in terms of p for...

I need some help. I am having a hard time find the recurrence when given an algorithm in c++. The algorithm is a Max search: Its where the program goes through the array from first element to last, or last to first (depends on how you program it) to look for the largest value. In this case it...