Recurrence Definition and 257 Threads

[PLAIN]http://img442.imageshack.us/img442/4514/ballsp.jpg The base case is 2^{K} = n (which turns into log_{2}n = k So I have a question on this recurrence relation problem. (I'm trying to get to make the top equation look like the bottom equation.) I know that the summation ends up becoming...

Homework Statement T(n) = 2T(n-1) T(1)=1 The Attempt at a Solution I am trying to show the iterations. T(n) = 2T(n-1) T(n) = 22T(n-2) T(n) = 222T(n-3) Is this the right track? Where the result would be 22222...1eventually? The problem just feels awkward D: If my answer is right is there...

Homework Statement Hello! I just want to be sure if I did solve the task correctly. The task is: Prove that bn is odd for integers n>=1 b1=1 b2=3 bk=bk-2+2bk-1 for k>=3 Homework Equations The Attempt at a Solution Induction basis: b1=1 true 1 is odd b2=3 true 2...

Use a recurrence relation to find the number of ways that stamps that have a value of 1 cent , 2 cents and a 3 cents can add up to eight cents. How exactly do you go about solving a problem like this without writing a program to find all the possibilities? The answer given is 81, but I...

Hi all Suppose that a_1=\sqrt5, a_{n+1}=a_n^2-2 and g_n=\frac{a_1a_2...a_n}{a_{n+1}}. Evaluate \lim_{n\rightarrow \infty } g_n. I have seen some information in http://oeis.org/search?q=3%2C7%2C47%2C2207&sort=&language=english&go=Search". Besides, the sequence gn seems as a good rational...

Hi, The problem is to solve (1-g_{i+1})P_{i+1}-P_{i}+g_{i-1}P_{i-1}=0 for P_{i} with boundary condition P_{i}=P_{i+L}, g_{i}=g_{i+L} Can anyone provide any guide of solving this type of recurence equation? Thank you!

Hi guys, would appreciate any help with this problem. It's from a graduate school entrance examination which I am practicing. problem statement When n is a natural number, the indefinite integral I_n is defined as I_n=\int\frac{1}{(x^2+a^2)^n}dx Here, a is a constant real number, and...

Homework Statement Dang it! More recurrence relation problems, but this time it’s due to a quadratic equation. Q. In the sequence u1, u2, u3,…,un, u1 = 0, u2 = 3, u3 = 12 and un = a + bn + cn2 Find the values of a, b and c. Homework Equations Provided at back of book…...

Homework Statement Hi! This is my first time on the site. I look forward to working with everyone…but hopefully not too much, assuming I‘m learning things correctly. :P My question pertains to Recurrence Relations, so here it goes… Foreword: The textbook I’m using actually supplies...

While solving a problem involving equilibrium positions of charges on a line, I came up with a recurrence relation which is nonlinear, and moreover implicitly defined. Here it is: x_{0}=0 and \sum^{n-1}_{i=0} \frac{1}{(x_{n}-x_{i})^{2}} = 1. I should also mention that 0 \leq x_{n}< x_{n+1} for...

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...

I am not sure how to format in LaTeX; I apologize for that. The Hermite polynomials Hn(x) (physicist's version) satisfy the recurrence relation, H_{n+1}(x) - 2xHn(x) + 2nH_{n-1}(x) = 0; H0(x) = 1 and H1(x) = 2x: Use this to derive the generating function for the Hermite polynomials...

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...

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 of z, right? I get: F(z) = z / (1 - z - z2)...