Recurrence Definition and 239 Threads

Homework Statement : [/B] I am just learning recurrence relations, and they are proving challenging.Homework Equations -- [/B]Let's have xn = 3xn-1 + 6xn-2. I wanted to look at it with two scenarios. The first is x0 = 1 and x1 = 3. The second is x1=3 and x2 = 4 The Attempt at a Solution Is...

A couple of times I have come across the suggestion that numerically evaluating a recursive relation in reverse can be a valuable approach. I can see this where, for example, the boundary conditions at one 'end' are inaccurate or undiscoverable. However, while the arithmetic of manipulating...

Given the image: http://i.stack.imgur.com/EJ3ax.jpgand that $x_0 = 1, y_0=0$ and $\text{angles} \space θ_i , i = 1, 2, 3, · · ·$ can be arbitrarily picked. How can I derive a recurrence relationship for $x_{n+1}$ and $x_n$? I actually know what the relationship is, however, don't know how to...

Homework Statement prove that s_k <= 2s_{k-2}+3 for all ints k >= 3 if s1=1 and s2 = 3 and s2=5 and s4=9The Attempt at a Solution base case k = 3 s_3 <= 2s_1 + 3 5 <= 2+3 that is true. Now i must prove the inductive step. This is where I am having trouble. I assume that s_k <= 2s_{k-2}+3...

Is Poincare' Recurrence Theorem (PCRT) considered a possible explanation for the "low entropy" initial conditions of the universe? Is the following a roughly correct paraphrasing of it? For a phase space obeying Liouville's theorem (closed, non-compress-able, non-decompress-able), the...

Keep in mind I am a complete layman when it comes to physics. Is the Poincare recurrence time the time it will take for the universe to be exactly in the state again as it is now or the time before the universe will even begin to be able to starting producing basic patterns from chaos? What is...

$$ T(n) = \begin{cases} 2 & \text{if } n = 2 \\ 2T(\frac{n}{2})+n & \text{if } n = 2^k \text{, for } k > 1 \end{cases}\\ \text{ } \\ \text{ } \\ \text{ } \\ \text{Prove } T(n) = n\lg(n) \text{ if } n = 2^k\text{, for } k > 1.$$ I am crawling through the "Introduction to Algorithms" textbook...

Not sure if Discrete Math is the correct category, but I'm looking for some idea / hint on how to tackle the following recurrence. $a_0 = 2$, and $a_{n+1} = 2a_{n} + \sqrt{3(a_n)^2 - 12}$ for $n \in \Bbb{N}$. Some attempts to massage the equation got me: $(a_{n+1}-a_n)^2 = 2a_na_{n+1} - 12$...

Why does the characteristic equation of a linear recurrence relation always look like an = series of constants multiplied by a number raised to n

Hello! (Smile) I want to find the exact solution of the recurrence relation: $T(n)=2T(\sqrt{n})+1$.$$m=\lg n \Rightarrow 2^m=n \\ \ \ \ \ \ \ \ \ 2^{\frac{m}{2}}=\sqrt{n}$$ So we have: $T(2^m)=2T(2^{\frac{m}{2}})+1$ We set $T(2^m)=S(m)$, so we get: $S(m)=2S \left( \frac{m}{2}\right)+1$...

Homework Statement [/B] Solve the recurrence relation (use iteration). an = an-1 + 1 + 2n-1 a0 = 0 Then prove the solution by mathematical induction. Homework EquationsThe Attempt at a Solution a1 = 2 a2 = 5 a3 = 10 a4 = 19 a5 = 36 The solution appears to be an = n + 2n - 1 How are we...

Hello! (Smile) Let $S(m)=S(m-1)+m$. I want to show that $S(m)=\Theta(m^2)$. That's what I have tried: We suppose a positive integer $m>0$. We suppose that $S(m-1)=\Theta((m-1)^2)$, so it holds that $\exists c_1, c_2>0$ such that : $$c_1 (m-1)^2 \leq S(m-1) \leq c_2(m-1)^2$$ We will show that...

Hey! :o I want to solve the following recurrence: $$T(n)=aT(n-1)+bn^c , T(1)=1$$ I have done the following: $$T(n)=aT(n-1)+bn^c \\ =a \left ( aT(n-2)+b(n-1)^c\right )+bn^c \\ =a^2T(n-2)+ab(n-1)^c+bn^c \\ =a^2 \left (aT(n-3)+b(n-2)^c\right )+ba(n-1)^c+bn^c...

Homework Statement ##T(n) = 2 T(\frac{n}{2}) + 2## ##T(1) = 2## Homework EquationsThe Attempt at a Solution I'm coming up with ##T(n) = n-1## on solving it by recursion tree method. But that's not the ans

Homework Statement ##T(n) = 2 T(n-1) + n, n \geq 2## ##T(1) = 1## Homework EquationsThe Attempt at a Solution I'm using recursion tree method to solve the above recurrence T(n) = Summation of non-leaf nodes + leaf nodes ##T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-1}##

Homework Statement If ##T(n+1)=T(n)+ \lfloor \sqrt{n+1} \rfloor , n \geq 1## ##T(1)=1## then ##T(m^2) = ? , m \geq 1## Homework EquationsThe Attempt at a Solution ##T(n)=T(n+1) - \lfloor \sqrt{n+1} \rfloor , n \geq 1## ##T(m^2)=T(m^2+1) - \lfloor \sqrt{m^2+1} \rfloor## ... ##T(m^2)=...

Solve each of the following linear recurrence relations: 1. t(1)=1 t(2)=4 t(n) - 5t(n-1) + 6t (n-2)= 0 for n>1 2. a(n)=4a(n-1) - 4a (n-2) with initial conditions a(0) = 4 and a(1)=12 3. t(1)=3 t(2)=3 t(n) + 2t (n-1) + t(n-2) = 0

Hello! (Wave) I want to use the master theorem, in order to find the exact asymptotic solution of $S(m)=4S \left ( \frac{m}{2}\right )+m^3 \sqrt{m}$. $$a=4 \geq 1, b=2>1, f(m)=m^3 \sqrt{m}$$ $$m^{\log_b a}=m^{\log_2{2^2}}=m^2$$ $$f(m)=m^{3+\frac{1}{2}}=m^{\log_b a+ \frac{3}{2}}$$ Thus...

Hello! (Wave) I want to prove that $T(n)=4 T \left ( \frac{n}{2}\right )+n^2 \lg n=O(n^2 \lg^2 n)$,where $T(n)$ is constant for $n \leq 8$, using the following method: "We choose a specific function $f(n)$ and we try to show that for an appropriate $c>0$ and an appropriate $n_0 \in...

Hello! (Wave) I want to find an asymptotic upper bound for the recurrence relation: $T(n)=9T \left (\frac{n}{3} \right ) + n^2 \log n $, $T(n)=c, \text{ when } n \leq 9$, using the following method: We choose a specific function $f(n)$ and we try to show that for an appropriate $c>0$ and an...

What method should i use to know if a recurrence relation is increasing or decreasing? i was given the following relation: A1 = 1 An=(An-1)^5 - 3 I know for sure it actually decreases since every term for n>=2 is a negative number raised to and odd number, but i don't know how to demonstrate...

Hello! (Wave) I want to prove by induction, that the solution of the recurrence relation $T(n)=2T \left ( \frac{n}{2} \right )+n^2, n>1 \text{ and } T(1)=1$ is $n(2n-1)$. We have to suppose that $n=2^k, k \geq 0$, right? Do I have to prove the solution by induction with respect to $n$ or to...

I was solving an integral and on the process of integration by parts it seems that I have a certain recurrence formula that I have to solve. Before I post it I want to understand how to solve a simpler case which is $$A(p,q) = A(p-1 , q ) +A(p,q-1) $$ where the base case $A(p,1)$ and $A(1,q)$...

I am given a formula in explicit form and as a recurrence relation. It is asked to derive the recurrence relation from the explicit form. How is this done?

Let $U_1,\,U_2,\,\cdots$ be a sequence defined by $U_1=1$ and for $n>1$, $U_{n+1}=\sqrt{U_n^2-2U_n+3}+1$. Find $U_{513}$.

Hello, it is known that given a certain recurrence relation that describes a sequence of numbers, it is often possible to obtain a function f[n] that directly yields the n-th number of the sequence. This is usually accomplished by using powerful techniques involving generating functions or the...

[SIZE="4"]Definition/Summary A recurrence relation is an equation which defines each term of a sequence as a function of preceding terms. The most well-known are those defining the Fibonacci numbers and the binomial coefficients. An ordinary differential equation can be considered as a...

A single pair (male and female) of rabbits is born at the beginning of the year. Assume the following: 1) Each pair is not fertile for their first month bet thereafter give birth to four new male/female pairs at the end of every month 2) no rabbits die a) let r_{n} be the number of pairs of...

Homework Statement Solve the recurrence relation an = 3an−1 −2an−2 +3, a0 = a1 = 1.Homework Equations an = general solution + particular solutionThe Attempt at a Solution I started with finding the general solution, which was easy. it ended up being A12n + A0 now I am having trouble solving...

Hi all, Could someone please explain to me the process involved in converting an inhomogeneous recurrence to a homogeneous recurrence, I'm completely confused as to how it works.Thanks

Problem: Let $a_0$ and $b_0$ be any two positive integers. Define $a_n$, $b_n$ for $n\geq 1$ using the relations $a_n=a_{n-1}+2b_{n-1}$, $b_n=a_{n-1}+b_{n-1}$ and let $c_n=\dfrac{a_n}{b_n}$, for $n=0,1,2,\cdots $. Write a)Write $(\sqrt{2}-c_{n+1})$ in terms of $(\sqrt{2}-c_n)$. b)Show that...

Homework Statement I'm given a recursive sequence with the following initial terms: ##\begin{matrix} f_0(0)=1&&&f_1(0)=0\\ f_0(1)=2&&&f_1(1)=1 \end{matrix}## Now, I'm asked to justify that we have the following recursive relations: ##\begin{cases} f_0(n)=2f_0(n-1)+f_1(n-1)\\...

Here is the question: I have posted a link there to this thread so the OP can view my work.

How to solve this question. Please explain step by step.

Here is the question: I have posted a link there to this thread so the OP can view my work.

Homework Statement Evaluate the following series ∑u(n) for n=1 → \infty in which u(n) is not known explicitly but is given in terms of a recurrence relation. You should stop the summation when u(n) < 10^(-8) u(n+1) = (u(n-1))^2 + (u(n))2 with u(1) = 0.5, u(2) = 0.6 Note 1:The lecturer...

I boxed the portion of the solution that I am questioning. How come the number of invalid strings is only 3n-1 - an-1 and not 3(3n-1 - an-1) ? As you can see there are three cases (Which are to the right of the black box) In all the three cases, the portion boxed in red is a string...

I am having difficulty knowing which "cases" include in the recurrence equation. My solution to problem in paint document. Cases 1 - 6: All cases contain strings of length n Let ak represent number of bit string of length k with a pair of consecutive 0s. For cases 1 and 2. an-1, k = n-1...

I'm trying to solve a third order recurrence relation but not sure how. I wrote the characterisitc polynomial and factored it into (x-1)^3. Now what?

A circuit has n switches, all initially off. In order to be able to flip the ith switch, the (i-1)th switch must be on and all earlier switches off. The first switch can always be flipped. Find a recurrence relation for the total number of times the n switches must be flipped to get the nth...

Find the number of ways to arrange three types of flags on an n foot flag pole: red flags (1 foot high), white flags (1 foot high), blue flags (3 feet high) Find a recurrence relation for this number with one condition that there cannot be three 1 foot flags in a row (regardless of their...

I'm in a problem where I have to solve the following functional equation : F(n)^2=n+F(n+1) Does anyone know some methods to solve this kind of problems ? A similar equation happens in Ramanujan example of root denesting : http://en.wikipedia.org/wiki/Nested_radical#Square_roots

I quote a question from Yahoo! Answers I have given a link to the topic there so the OP can see my response.

Here is the question: I have posted a link there to this topic so the OP can see my work.

Helloo! I have to solve the following recurrence relations: (a) T(n)=sqrt(2)*T(n/2)+lgn (b) T(n)=3*T(n/4)+nlgn (c) T(n) 3*T(n/3)+n/2 (d) T(n)=5*T(n/2)+Θ(n) (e) T(n)=9*T(n/3)+O(n^2) Could you tell me if my results are right? Using the master theorem I found: (a)T(n)=Θ(sqrt(n)) (b)T(n)=Θ(nlgn)...

Here is the question: Here is a link to the question: Pre Calculus homework help please!? - Yahoo! Answers I have posted a link there to this topic so the OP can find my response.

Hello!Could you help me at the exercie below? Consider a gamble,with the same possibility to win or to lose.If we win,we double our property,but if we lose we halve our property.Let's consider that we begin with an amount c.Which will be the mean value of our property,if we play n...

Just an easy one to start off with, find a non-recursive formula for the $n$th term of the following linear homogeneous recurrence: $$a_0 = 2, ~ ~ a_1 = -2, ~ ~ a_n = -2 a_{n - 1} + 2 a_{n - 2} ~ ~ \text{for} ~ n \geq 2$$ Hint:

Homework Statement a_{n} = a_{n-1} + n a_{0} = 0 The Attempt at a Solution h_{n} = h_{n-1} t^{2} - t = 0 t=0 t=1 h_{n} = B p_{n} = bn + c p_{n} = p_{n-1} + n bn + c = b(n-1) + n bn + c = (b+1)n -b I'm sure I've gone wrong somewhere, I just can't figure out where!

Here is the question: Here is a link to the question: Find The Closed Form? - Yahoo! Answers I have posted a link there to this topic so the OP can find my response.