Questions regarding functions defined recursively, such as the Fibonacci sequence.

learn more… | top users | synonyms (2)

0
votes
1answer
74 views

Solve $a_{n+1} - a_n = n^2$ using generating functions

The Full Question Using the method of generating functions, solve $a_{n+1} - a_n = n^2$ where $a_0 = 1$ My Research Scanned the website for similar answers, reviewed the following links: Solve the ...
0
votes
2answers
46 views

How to deduce sum's result?

I was solving some tricky-task with algorithms and I obtained following reccurence: $$a_{k+1} = 4a_{k} + 16^{k}, a_{1} = 1$$ It's obvious that with given start condition: $$a_{k+1} = 4a_{k} + 16^{k} ...
0
votes
1answer
33 views

Polynomials: functions of functions integer roots

I'm attempting to prove: Define functions $f_m$ by the recursion relation such that $f_1(x) = 2x^2-1$ and $f_k(x) = f_1(f_{k-1}(x))$ . Then for all $ m > 0$, there exists no $x \in \mathbb Z$ ...
0
votes
2answers
47 views

Solve the recurrence relation (using iteration?)

$a_n = a_{n-1} + 1 + 2^{n-1}\\ a_0 = 0$ Not sure how to iterate with the exponent term. Here's what I got: $= (a_{n-2} + 1 + 2^{n-1}) + 1 + 2^{n-1} = a_{n-2} + 2 + 2(2^{n-1})\\ = (a_{n-3} + 1 + ...
0
votes
1answer
46 views

Solve the Recurrence

Solve the recurrence $a_k = 2a_{k-1} + 3a_{k-2}$, if $a_0 = 0$ and $a_1 = 8$. I understand how to get the generating function: $$G(x) = \sum_{k \geq0}a_kx^k = a_0 + a_1x + \sum_{k\geq 0}a_kx^k = 8x ...
0
votes
4answers
52 views

How to prove the sequence given by $a_{n+1}=s+a_n^2$ is monotonic increasing?

Let $s$ be $0\:\le \:s\le \:\frac{1}{4}$ and consider this sequence: $a_1\:=\:s$ $a_{n+1}\:=\:s\:+\:a_n^2$ I want to prove that is monotonic sequence, so I thought about induction or assume in ...
0
votes
1answer
45 views

$\lim_{n\rightarrow \infty} a_n$ for $ a_{n+1} =a_n\cdot \frac{6+a_n}{3+2a_n}$

let there be $a_1=3$,$a_{n+1} =a_n\cdot \frac{6+a_n}{3+2a_n}$ so $a_1=3,a_2=3,etc...$ let assume there is a limit L so $L =L\cdot \frac{6+L}{3+2L}$ L=0,3 But that is not a proof, how do I continue ...
0
votes
3answers
39 views

Solving $ax_{n+1}+bx_n+cx_{n-1}=0$

In a book I found the following: Consider a recurrence relation of the form $$ ax_{n+1}+bx_n+cx_{n-1}=0 $$ where $a$ and $c$ are both non-zero. Let us try a solution of the form ...
0
votes
2answers
44 views

prove $S(n) \leq (5/2)^n$

I've been flipping through my math book for nearly 5 hours working on these recursive problems and it's just not clicking. I have a recusrive sequence $S(0) =1$ $S(1)=2$ $S(n) = 2S(n-1) +S(n-2)$ ...
0
votes
1answer
113 views

Gambler's ruin and coin toss

Edit 3. Fixed question to be more clear and include current solution Problem Two players player 1 and player 2 plays a game of fair coin flipping. Player 1 starts with $A$ coins and Player 2 with ...
0
votes
2answers
52 views

Closed form formula for the given product

I'm working on a recurrence which give me the following solution: $$ f(n)=(2+1)(2+\tfrac12)(2+\tfrac13)\cdots\left(2+\tfrac1{\lg(n)}\right) $$ so for $n=16$, $f(n)$ is just like: $$ ...
0
votes
1answer
177 views

Bounding error when iterating a function

If I am iterating some function $f$ that goes to infinity as x goes to infinity with error $o(g(x))$, for example, is there anyway to bound the error? To be more specific, if I have some sequence ...
0
votes
3answers
79 views

Finding general formula for a recursion function

If we have a recursion relation defined as $a_n = 3a_{n-1}+1$ with $a_1=1$ then find the general formula for $a_n$ in terms of $n$ with a(1) = 1. So far I have: $a_n = 3a_{n-2}+1+1 = 3a_{n-3}+1+1+1 ...
0
votes
2answers
149 views

Why do we use the term “equivalent” with Operators but “equal” with Functions?

Why do we speak in terms of "equality" when we deal with functions but "equivalence" when dealing with operators? To elaborate: Two functions, f and g are equal to each other (denoted: f=g) if: ...
0
votes
2answers
45 views

Find the values of $r_1, r_2, r_3$ in the recurrence relation $a_n = r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $

Consider the recurrence relation $a_n = > r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $ for $n \ge 3$. The roots of the characteristic polynomial are $x = -1$ of multiplicity 2, $x= 3$ of ...
0
votes
1answer
37 views

How $L_n = L_{n-1} + n $ become $L_{n-2} + (n-1) +n $ and So on?

I am currently reading 'concrete mathematics' of knuth. I don't know how $L_n = L_{n-1} + n $ become $L_{n-2} + (n-1) +n $ and finally $L_0+1+2...+(n-2)+(n-1)+n $ can you please tell me?
0
votes
2answers
45 views

Is there a difference for discount per unit and discount per purchase total?

I can't find relevant tags for my question so I wonder if this is a good place to ask. I wanted to ask this a long time ago but keep forgetting. Let's suppose when shopping for 3 units of specific ...
0
votes
1answer
32 views

Going from recurrence relations to closed form

How do I go from the following recurrence relation a(n) = (n+1)a(n-1) where a(0) = 2 to a closed form? I know I need to use an iterative approach but I am not ...
0
votes
2answers
52 views

Recurrence Relationship Questions

Consider the recurrence defined by: $$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$ Determine what Gn is for several values of n to determine a formula for Gn. $2n$ $n$ $2n-1$ $n^2$ *I believe this one is ...
0
votes
2answers
48 views

Two sequences $a$ and $b$ for which $\Delta a_n = \Delta b _n$

Find two different sequences $a$ and $b$ for which $\Delta a_n = \Delta b_n$ for all of $n$. This is my first time doing recurrence relations, so if anyone could provide some thorough and clear ...
0
votes
2answers
47 views

Solve Fibonacci-like linear recurrence equation

How to solve the following equation: $f(n) = f(n-1) + f(n-2) + 1$ My best guess is that it has something to do with Linear Recurrence Equation. I know how to do it without the constant $1$, which ...
0
votes
2answers
64 views

Ways to add a number using just 1's, 5's, 10's, 25's, 50's

given the set $\{1, 5, 10, 25, 50\}$, in how many ways, can you combine this numbers to get a specific number. For example, 11 can be shaped as $1\cdot11$, or $5\cdot112 + 1\cdot111$, or $10\cdot111 + ...
0
votes
1answer
78 views

How to solve this recurrence of a sequence?

$x_1=1$, $x_2=2$, $x_n=n\cdot x_{n-1}+\frac{n(n-1)}{2}x_{n-2}$ Thanks to Barry Cipra's suggestion, now I have obtained the solution for $x_n$: ...
0
votes
1answer
54 views

Master Theorem Question

I need to solve the following: $T(n)=T(n-1)+8$ I've tried doing $a=1$, $b=-1$, and $d=8$ but $\log_{-1}1$ doesn't make sense. Any suggestions?
0
votes
1answer
85 views

How many words can you make with {1,2,3,4} such that difference between 2 letters is 1

Hello and happy new year. I've been struggling with this question and I really need some help. The question is, find a recurrence relation that demonstrates how many words of length $n$ can we write ...
0
votes
2answers
123 views

Prove (1 + x)^n + (1 - x)^n < 2^n by using Binomial Theorem

Hi my boss asked me to resolve this equation: Prove (1 + x)^n + (1 - x)^n < 2^n by using Binomial Theorem -1 < x < 1 ...
0
votes
2answers
53 views

Number of ways to arrange n identical stones into piles

Given, there are n stones which are identical. How many ways can the stones be arranged into piles. Suppose if n=4 , we can make one pile with 4 stones or 2 piles with 3,1 or 2,2 or 3 piles with 1,1,2 ...
0
votes
3answers
227 views

Recurrence relations problem

Don't understand why someone would assign problems that he hasn't reviewed... It's crazy... I ask for help and got that response lol If $S_{n+2} = 2S_{n+1} - S_n + 3$, what are the correct steps in ...
0
votes
1answer
52 views

Solve non-linear recurrence

I am trying to solve the following recurrence (i.e. determine $a_n$). I'm not entirely sure how to proceed, I have only encountered linear ones so far. This is not a homework, I'm just doing it for ...
0
votes
1answer
126 views

Limits of a recursively defined sequence [closed]

Let $x_1=a$ and define a sequence $\left(x_n\right)$ recursively by: $x_{n+1} = \dfrac{x_n}{1 + \frac{x_n}{2}}$ For what values of $a$ is it true that $x_n$ approaches $0$?
0
votes
2answers
705 views

Finding the closed form solution of a third order recurrence relation with constant coefficients [duplicate]

How would you solve for the closed form solution of a(n) given the general form of the third order linear homogenous recurrence relation with real constant coefficients. ...
0
votes
2answers
90 views

A basic problem on recurrence relation

How to solve this recurrence relation $a_n=(1-p) + (2p-1)a_{n-1}, n \geq 2$ where $a_1= \beta$ and $p$ some arbitrary number.
0
votes
4answers
322 views

How do I derive a characteristic equation for this specific recurrence relation?

I have no problems solving recurrence relations with two roots, but I've just encountered one with one root: $c_{n+1} = 3c_{n}+1$ such that $c_{0} = 0$. In my solving process, I suppose I've gotten ...
0
votes
3answers
91 views

What are the coefficients of the polynomial inductively defined as $f_1=(x-2)^2\,\,\,;\,\,\,f_{n+1}=(f_n-2)^2$?

Let $\{f_n(x)\}_{n\in \Bbb N}$ be a sequence of polynomials defined inductively as $$\begin{matrix} f_1(x) & = & (x-2)^2 & \\ f_{n+1}(x)& = & (f_n(x)-2)^2, &\text{ for all ...
0
votes
2answers
48 views

Finding a closed form for $x_{k+1}=\frac{1}{3}+\frac{k-1}{2}+x_k$ [closed]

I have a sequence $\{x_n\}$ such that $x_2=\frac{7}{6}, x_3=\frac{5}{2}$ and $x_{k+1}=\frac{1}{3}+\frac{k-1}{2}+x_k$. I want to find the $x_l$. I know that this is a problem of recurrence relation. ...
0
votes
1answer
267 views

$n$ Lines in the Plane

How am I to "[u]se induction to show that $n$ straight lines in the plane divide the plane into $\frac{n^2+n+2}{2}$ regions"? It is assumed here that no two lines are parallel and that no three lines ...
0
votes
1answer
103 views

Generating The Series

This is related to an ongoing event. It involves generating the following series : http://oeis.org/A008826 The generating Function as given in the above link is : ...
0
votes
2answers
106 views

Recursive function into non-recursive

I have to express $a_n$ in terms of $n$. How do I convert this recursive function into a non-recursive one? Is there any methodology to follow in order to do the same with any recursively defined ...
0
votes
1answer
50 views

Predictions for recurrence relations

Given the recurrence relation $a_n = 2a_{n-1} + a_{n-2}$ $a_0 = 1$ and $a_1=1$ Is it true that $a_n < 6a_{n-2}$ for all $n\ge4$ I'm not really sure how to go about solving this problem. I've ...
0
votes
3answers
76 views

Still stuck on recurrence

I am still stuck on this problem and it is very frustrating. I need to solve this using exponential generating series and again with telescoping. Problem is I am not even sure what telescoping is and ...
0
votes
1answer
95 views

What is the closed form for the general recurrence relation?

$T(N) = a\cdot T(N-b) + c \cdot N + d $ $T(0) = 0$ I honestly don't understand this concept at all. Any help would be great.
0
votes
3answers
219 views

Power series and recurrence

Please help me find the radius of convergence and the value of the following power series: $\sum_{n=0}^{\infty} a_nz^n$, when $a_0=1,a_1=-1$, and $3a_n+4a_{n-1}-a_{n-2}=0$ for $n>1$.
0
votes
1answer
214 views

recurrence and fibonacci [closed]

could someone possibly help me with a proof. prove $a_n = F_{2n-1}$ for fibonacci numbers and a recurrence relation where $a_1 = 1$ $a_2 = 2$ $a_3 = 5$ $a_4 = 13$ $a_5 = 34$ 89,233,610,1597 ...
0
votes
2answers
138 views

convert generating function to recurrence

How do we convert generating function to a recurrence: Lets say we have this function \[ x\mapsto x\cdot \frac{8+2x-2x^2}{1-6x-3x^2+2x^3} \] how do we get it back to a recurrence?
0
votes
1answer
113 views

Question about Rolle's theorem

Suppose $f(x)$ is continuous on a closed interval $[a,b]$ and differentiable on the open interval $(a,b)$. I would like to prove the existence of $c$ such that $$ (c-a)\cdot(b-c)\cdot\ f'(c) = ...
0
votes
2answers
66 views

Subtracting lower-order term to prove subtitution method works

Substation method fails to prove that $T(n) = \Theta(n^2) $ for the recursion $T(n)= 4T(n/2) + n^2$, since you end up with $T(n) < cn^2 \leq cn^2 + n^2 $. I don't understand how to subtract off ...
0
votes
2answers
2k views

How to derive and solve a difference equation.

I am having terrible trouble with the following question: Suppose that $x_n$ is the amount owed on a mortgage after n years, £$m$ is the monthly repayment and $r$ is the annual percentage interest ...
0
votes
2answers
521 views

solve recurrence relation $a(n)=2a(n-1)+1$ [duplicate]

Possible Duplicate: Solving a Recurrence Relation/Equation, is there more than 1 way to solve this? I am trying to solve following recurrence relation $$a(n)=2a(n-1)+1\;.$$ I have divided ...
0
votes
3answers
662 views

Solving Simple Recursive Equations

For recursive equations of the form $au_{n+2}=bu_{n+1}+cu_n$ I read that the trick is to let $u_n=\lambda^n$ for some $\lambda$ and then find an appropriate $\lambda$ that fits the initial conditions. ...
0
votes
1answer
87 views

Can we express $p_n$ in terms of $p_0, p_1$ and $n$?

$p_0=a$, $p_1=b$, $bp_n=p_{n+1}+p_{n-1}$ express $p_n$ in terms of $a,b,n$. Any help would be appreciated, because you guys are splendid.