Recurrence Definition and 239 Threads

Homework Statement Find a recurrence relation for the number of stricly increasing sequences of positive integers that have 1 as their first term and n as their last term, where n is a positive integer. that is, sequences a1, a2, ..., ak, where a1 = 1, ak = n, and aj < aj+1 for j = 1, 2...

Here is the question: Here is a link to the question: Discrete Math Help questions? - Yahoo! Answers I have posted a link there to this topic so the OP can find my response.

Hi I've got a recurrence relation: x_n = a*x_(n-1) + b; I think I'm going mad trying to figure out a closed form, eg. x(n) = ? the nth iteration Is there a trick or something I'm missing? Thanks

This question is related to the question that I have asked here, although the equation is ever so slightly different: http://www.mathhelpboards.com/f15/solving-specific-variable-when-solving-recurrence-equation-3804/ I have a recurrence equation of the form $$ T(n) = 0, n = 0, n = 1\\ T(n) =...

I have the following recurrence equation, where C is just some constant: $$ T(n) = 0, n = 1\\ T(n) = T(\frac{n-1}{2}) + 2C, n > 1 $$ Using a top-down approach to unrolling the equation to find the pattern, I get: $$ T(n) = T(\frac{n-k}{2^{k}}) + 2kC $$ Now I want to solve for k and associate...

Fluctuation theorem says that there will be fluctuations in microscopic scale that results local decreases in entropy even in isolated systems. According to the Poincaré recurrence theorem, after sufficiently long time, any finite system can turn into a state which is very close to its initial...

Here is the question: Here is a link to the question: Discrete Mathematics Question? - Yahoo! Answers I have posted a link there to this topic so the OP may find my response.

Here is the question Here is a link to the question: 2nd order homogeneous linear recurrence? - Yahoo! Answers I have posted a link there to this topic so the OP can find my response.

I posted a link to this topic, so the OP could find my response. Here is a link to the original question: Recursive formula help on real world situations? - Yahoo! Answers Let $A(t)$ represent the amount, in mg, of antibiotic in Jonah's bloodstream at time $t$, measured in hours. With a...

Homework Statement Let d0, d1, d2,... be defined by the formula dn = 3n - 2n for all integers n ≥ 0. Show that this sequence satisfies the recurrence relation. dk = 5dk-1 - 6dk-2.Homework Equations The Attempt at a Solution I found that dk = 3k - 2k dk-1 = 3k-1 - 2k-1 dk-2 = 3k-2 - 2k-2...

Homework Statement Given binary string of length n. substrings of 1's should be even. (given 0 is a delimeter) eg) 10111 is broken down into 1 and 111 (all odd) so, for example string with H(n = 4) 0000 1100 0110 0011 1111 there are 5 of them. H(n = 3) 000 110 011 there are 3 of...

I have a linear recurrence sequence and am having a problem understanding what to do when the ratio does not seem to be the same between each of the terms, so Terms; 4, 1.4, 2.44, 2.024... (n = 1,2,3...) How do I find a the ratio of these terms, and if there is none, please advise how I...

Homework Statement I'm working on problem 6.11 in Bransden and Joachain's QM. I have to prove 4 different recurrence relations for the associate legendre polynomials. I have managed to do the first two, but can't get anywhere for the last 2 Homework Equations Generating Function: T(\omega...

Find a simple closed formula for the ordinary generating function of the sequence given by {a_{n}]}n>=0 when a_{n} is given by a_{n} = 6 * 5^n - 5 * 3^n. My question is how do you find the recurrence relation a_{n} = 6 * 5^n - 5 * 3^n. I don't know were to start.

Hello, It is my understanding that if we have a sequence defined as follows:an+1=(ψ)an + (λ)Then if ψ≥1 or ψ≤-1, the sequence diverges. If -1<ψ<1, the sequence converges to: λ/(1-ψ)I was working problems in a book and one of the problems said that the following sequence converges...

There exists Green's Functions such that the solutions appear to be retro-causal. The Klein-Gordon equation allows for antiparticles to propagate backwards in time. Does this mean the future can influence the past and present? Then again The Poincare Recurrence Theorem states that over a...

Homework Statement Solve the recurrence: T(n) = T(n/7) + T(4n/5) + n for n > 35 with base case T(n) = constant for n ≤ 35.Homework Equations The Attempt at a Solution Is this mathematical induction? No idea how to do this one.

Hello, I have the following recurrence equation $$T(n)=aT(n-1)+bn$$ Using substitution, I have solved it to the following form $$T(n)=a^{n-1}+b \sum_{i=2}^{n}ia^{n-i}$$ Now I am trying to prove my solution is correct using induction, but I'm a bit lost. Any advice on how to conduct this...

My book wants to find solutions to Legendre's equation: (1-x2)y'' - 2xy' 0 l(l+1)y = 0 (1) By assuming a solution of the form: y = Ʃanxn , the sum going from 0->∞ (2) Now by plugging (2) into (1) one finds: Ʃ[n(n-1)anxn-2-n(n-1)anxn - 2nanxn + l(l+1)anxn = 0...

Homework Statement Find the general solution to the following recurrence relations (defined n≥2). c) an=6an-1-9an-2+8n+4 Homework Equations The Attempt at a Solution an=6an-1-9an-2+8n+4 8n+4= an -6an-1+9an-2 R2-6R+9=0 R=3,3 So hn=A(3)n+B(3)n Assume pn=Cn+Cn2 → This is where I got...

x_{xn-1}= 5_{xn-1} - 6_{xn-2};for \ n≥2 \\ x_{1}=1 \\ x_{0}=0 prove by induction that: \begin{bmatrix} x_{n}\\ x_{n-1} \end{bmatrix} = \begin{bmatrix} 5 &-6 \\ 1 & 0 \end{bmatrix}^{n-1}\begin{bmatrix} 1\\0 \end{bmatrix}

Hi guys. I'm having a bit of trouble with what I thought was a simple math question. Homework Statement x_{n} = \int_0^1 \frac{t^n}{t+7}dt Show that x_0=ln(8/7) and x_n = n^{-1} - 7x_{n-1} 2. The attempt at a solution Showing x0 = ln(8/7) is a vanilla textbook log question. I'm having...

Homework Statement The problem along with its solution is attached as Problem.jpg. Homework Equations Recurrence relation. The Attempt at a Solution I am confused as to what the solution is stating. I get up to and including (3) but I am stuck at (4). After (4), I get that k = log2(n)...

I have a question; help is welcome. Let sn be a linear, non-homogeneous recurrence sequence, and let hn be a corresponding homogeneous sequence (with initial values to be determined). As it turns out, the offset between the two (sn - hn) is given by the steady state value of sn, if the...

This is how Wikipedia summarizes the Poincaré Recurrence Theorem: This is wrong, isn't it? Don't you need to ensure the phase space is bounded, and isn't conservation of energy an insufficient justification for that? Like, imagine throwing two baseballs away from each other into infinite...

Homework Statement Hello. I am trying to prove a result that I have been making use of, but never really proved. Consider the recurrence equation x(k+1) = 0.5 x(k) + u(k), where u(k) is a bounded sequence. For this problem, assume that u(k) goes to zero. I want to prove that x(k) goes to...

So my professor gave us this recurrence relation to prove combinatorially for extra credit, but I was unable to figure it out. h(n) = 5h(n-1) - 6h(n-2) + 1 This was my solution, but I couldn't figure out how to factor in the +1: Let hn be the number of ways to arrange 0,1,2,3,4 on a 1xn...

Homework Statement For n ≥ 1, let g(n) be the number of ways to write n as the sum of the integers in a sequence of any length, where each integer in the sequence is at least 2. For n≥3, show that g(n) = g(n-1) + g(n-2).2. The attempt at a solution I've gone through values of g(n) for...

Homework Statement Hello, This expression was derived from a polygon word problem and I need to find a closed form for it with repeated substitution (I think). T(k, n) = T(k, n-1) + (k-2)(n-1) + 1 Homework Equations The Attempt at a Solution Get a pattern like: = T(k, n-2) + (k - 2)(2n -...

I have been working on a problem proposed in a math journal, and there is only one thing I need to figure out. Here it is: Let (a_n) be a sequence defined by a_1 = a and a_{n+1} = 2^n-\sqrt{2^n(2^n-a_n)} for all 0 \leq a \leq 2 and n \geq 1. Find \lim_{n \rightarrow \infty} 2^n a_n in terms...

If I have a recurrence equation of the following form: $$T(n) = T(km) = a, m = 1$$ $$T(n) = T(km) = T(k) + T(k(m-1)) + cn, m > 1$$ Where a is simply a constant, and k is an integer constant > 0. Now I begin substituting to find the pattern: $$T(k) = a$$ $$T(2k) = a + [a] + c2k$$ $$T(2k) = 2a...

I have a recurrence equation of the form T(n) = aT(n - 1) + bn where T(1) = 1. In trying to solve this equation, I have tried a top-down and bottom-up approach of "unrolling the equation" but found that I am still having trouble and am unable to solve. Any advice would be appreciated.

I have a linear recurrence sequence, 3, -1.5, 0.75, -375 x = a a = 3 x2, = -1.5, x3, = 0.75, x4 = -375... x2 = rx1+d x3 = rx2+d -1.5 = 3r + d 0.75 = -1.5 + d -1.5 - 0.75 = (3r + d) - (-1.5 + d) r = - 0.5 Sub in equation (2) d = -1.5 - 3r = -1.5 - 3(-0.5) d = 0 x4 = -0.5 x 0.75 + 0 =...

I'm doing a much larger problem and I am stuck going from: T(n) = 14 + T (n − 2) + 10(n + (n − 1)) to T(n) = (n − 1)7 + T(1) + 10(Σi=2 to n of i) and I would very much appreciate it if someone could show me the detailed steps. (I've been told something about expanding the recursive...

Hey! I was trying to find the expected time an algorithm takes to solve a certain problem, and I ended up in a very nasty recurrence relation of this form: a_{k,k} =...

1. Solve the following recurrence relation. an - 5an-1 + 6an-2 = 0, n ≥ 2, a0 = 1, a1 = 3 3. My attempt I changed it to 0 = tn - 5tn-1 + 6tn-2 Don't know where to go from there.

Solved!

Hi all Suppose that , 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 this link. Besides, the sequence gn seems as a good rational approximation for \sqrt5. I know that the answer is 1, But I can't find any...

Homework Statement I need to solve a recurrence equation in order to perform algorithm analysis. I got the recurrence from the algorithm I developed. It's been years since I did my undergrad degree and my maths is rusty. Homework Equations T(n)= 1+ \sum_{i=1}^n2(n-i+T(i)) The Attempt...

Hi My calculus textbook is completely crap at explaining recurrence relations. I know the theorems needed to solve difference equations analytically, but I do not understand why they are true. What websites and/or books can I read to get a better intuitive understanding of recurrence...

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