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

learn more… | top users | synonyms

2
votes
1answer
66 views

Generating functions over $\mathbb{Z}$

Let $(a_n)_{n \in \mathbb{Z}}$ be a sequence such that both limits $\lim_{n \to \infty} a_n$ and $\lim_{n \to -\infty} a_n$ exists. Consider recursive relation $$ 2b_n - \frac{1}{2}(b_{n-1} + b_{n+1}) ...
1
vote
2answers
80 views

How do I find $\sum_{i=1}^n\frac{1}{x_i}$ where $x_i = x_{i-1} + \frac{1}{x_{i-1}}$

I have a recurrence: $x_n = x_{n-1} + \frac{1}{X_{n-1}}$. I need the value of n for which $x_n$ IS CLOSEST TO $2*x_0$, where $x_0$ is a positive integer. I tried the following: $x_1 = x_0 + ...
1
vote
0answers
35 views

Finite geometric sequence with a ratio greater than 1

I am trying to solve the recurrence relation: $ t(n)= 3T(n/2)+Cn$ (if $n>2$) $t(2)=C$ (otherwise) I know that there is the Master Theorem but I am trying to use the tree method. This ...
2
votes
1answer
31 views

Solving recurrence

Can anyone help me solving this recurrence? I don't see how I could use Master Theorem for this one and I couldn't find anything that would give me some idea how to do this. $$ T(n) = ...
1
vote
2answers
62 views

Counting numbers with the digit 5: How to express recurrence relation in closed form?

I figured out the algorithm for finding the count of numbers containing the digit 5 for any power of 10. What is the correct way to express y in this formula? $f(x) = 9y + (x/10)$ Where y is ...
0
votes
0answers
23 views

Functional Relationship Question on Analytic Geometry

I am solving some problems on analytic geometry. I have a set of points $\{P_1,P_2,P_3,...,P_k\}$ from wich $P_1,P_2$ are known. The rest have coordinates $P_n\big(x_n,y_n\big)$ and for any value of ...
5
votes
2answers
149 views

Let $x_{n+1} = x_n + 1/(x_1 + x_2 +\ldots + x_n)$ with $x_1 = 1$. Show that $x_n\sim\sqrt{2\log(n)}$.

As the title states we have a sequence defined by $$x_{n+1} = x_n + \dfrac{1}{x_1 + x_2 + \cdots + x_n}$$ with $x_1 = 1$. The first few terms are: $1, 2, \frac{7}{3}, \frac{121}{48} \cdots$ Any ...
0
votes
1answer
44 views

Problem with making explicit formula from recursive formula

I'm having trouble turning this recursive formula into explicit one $a_0 = 0,\\a_{n+1} = a_n(1 - b_n) + b_n,$ where $(b_n)$ is given sequence of real numbers.
0
votes
1answer
67 views

Understanding Recurrence Relation

as i ask question and answered by some Clever people at this topic: Recurrence Relation Solving Problem i try to learn new thing with new question very similar to get familiar with recurrence ...
6
votes
0answers
40 views

Recurrence relations with multiple roots of auxiliary equation

Suppose we have a homogeneous linear recurrence relation of the form $$u_{n+r}+a_1u_{n+r-1}+\dots +a_ru_n=0$$ The auxiliary equation is then $$f(x)=x^r+a_1x^{r-1}+\dots +a_r=0$$ It is well known that ...
1
vote
1answer
25 views

recursive relation for putting signs in 2*n table

Consider we have a $2\times n$ table and we want to put a sign in some of the cells, and we don't put signs in both adjacent cells give a recursive phrase that shows that how many ways we can do that? ...
0
votes
2answers
132 views

Recurrence Relation Solving Problem

Can anyone help me in solving this complex recurrence in detail? $T(n)=n + \sum\limits_{k-1}^n [T(n-k)+T(k)] $ $T(1) = 1$. We want to calculate order of T. I'm confused by using recursion tree ...
0
votes
2answers
41 views

Divide and Conquer Recurrence Relation help?

So the divide and concur recurrence has to be of the form H($n$) = $a$H($n$/$b$) + $cn^d$. I already figured out that $a$ = 4 and $b$ = 2. I am really stuck on how to find $cn^d$ however. I ...
1
vote
3answers
37 views

Finding an exact solution to a difference equation

How would I solve an equation of the form: $u(n+1)=1/2u(n)+(1/3)^n$ when $u(0)=1$? I got an answer of the form $u(n)= c + \sum(1/3)^j*2^{j-1}$ but believe this is incorrect?
0
votes
1answer
27 views

Particular solution of recurrence relation

I've got this recurrence relation: $$M_n = M_{n-1} + n(2n-1)|M_0 = 0$$ and can't think of any form of particular solution to get a solvable constant. With $M_n^H = K$being the homogeneous part of ...
1
vote
2answers
53 views

Is there a standard recurrence relation to solve this?

I have infinite supply of $m\times 1$ and $1\times m$ bricks.I have to find number of ways I can arrange these bricks to construct a wall of dimensions $m\times n$. My problem is how can I approach ...
0
votes
1answer
45 views

Stirling number of the second kind recurrence relations

I am interested to understand why the following recurrence relations of the Stirling number so the second kind hold using counting arguments ...
3
votes
4answers
76 views

Solving a recursion relation: $a_{n+1}=-3a_n+4a_{n-1}+2$

I'm having trouble solving this recursion relation. I believe it's a non-homogeneous one. Here it is: $$a_{n+1}=-3a_n+4a_{n-1}+2$$ Really, I am just having trouble with the particular solution. The ...
4
votes
2answers
88 views

How to *really* solve a non-homogeneous recurrence

First let me state that I am not asking about the usual procedure for finding a trial solution to a non-homogeneous recurrence. I have been doing this for many years and can solve all the basic ...
10
votes
3answers
177 views

Show that $2^n(\cos^n(\frac{2\pi}{9})+\cos^n(\frac{4\pi}{9})+\cos^n(\frac{8\pi}{9}))\in\mathbb{Z}$

$a_n=2^n\left[\cos^n\left(\dfrac{2\pi}{9}\right)+\cos^n\left(\dfrac{4\pi}{9}\right)+\cos^n\left(\dfrac{8\pi}{9}\right)\right]$. Show that $a_n\in\mathbb{Z}$ for all $n\in\mathbb{Z}$. Find the last ...
2
votes
1answer
108 views

Integral involving the Spherical Bessel Function of the First Kind

How can I prove the equation below using Spherical Bessel Function Recurrence Relation? (where $ j_{n}(x) $ means Spherical Bessel function of first kind) Definition using BesselJ function: $$ ...
-1
votes
4answers
108 views

How do I find $f(4)$ when $f(n)= f(n-1)+ 2n$?

Can somebody please help me find $f(4)$ when $f(n)= f(n-1)+ 2n$? $f(1)$ equals $16$ by the way.
1
vote
2answers
74 views

Find the general term of the recursive relation $a_{n+1}=\frac{1}{n+1}\sum\limits_{k=0}^n a_k 2^{2n-2k+1}$

I need to find the general term of the recursive relation $a_{n+1}=\frac{1}{n+1}\sum\limits_{k=0}^n a_k 2^{2n-2k+1}$ I know it's the central binomial sequence but I can't find a way to show it. ...
1
vote
4answers
67 views

A sequence was defined by a equation

The sequence was defined by the equations: $${a}_{1}=a\left(\in R \right),{a}_{n+1}=\frac{2{{a}_{n}}^{3}}{1+{{a}_{n}}^{4}},n\geq 1.$$ show that $\left(a \right)$The given sequence is convergent. ...
1
vote
0answers
49 views

Proof that $\forall x \in \mathbb{R}, \forall n \in \mathbb{N}: (f(x))^n = f(nx)$ only has solutions of the form $f(x) = c^x$ for some constant $c$

I am looking for a proof (or a counterexample I suppose) that the recurrence equation (is that the right term here?) $(f(x))^n = f(nx)$ only has a solution of the form $ f(x)=c^x$ for some ...
0
votes
3answers
58 views

Finding a reduction formula for this integral

Let $$I(n)=\int_0^1 (x-x^2)^n dx .$$ Mainly, what I'm trying to get is a recurrent form of this integral that probably involves $I(n-1)$. My attempt ...
1
vote
2answers
35 views

First order recurrence relation

I have to solve this relation: $$a_1 = k \\ a_n = \frac{10}{9} a_{n-1} + k + 1 - n$$ (k is constant) How can I do it??
1
vote
1answer
33 views

How to convert linear recurrence to a tiling question

If I have some linear recurrence of form $$f(n) = a_1f(n-1) + a_2f(n-2) + a_3f(n-3) + \cdots + a_kf(n-k)$$ How does this translate to tilings? For example the Fibonacci sequence is the same as ...
0
votes
1answer
63 views

Solve the recurrence relation $f(n) = f(n - 1) + f(n - 2) + f(n - 3)$

This is a problem I was playing with that troubled me greatly. $f(n) = f(n - 1) + f(n - 2) + f(n - 3)$ $f(1) = f(2) = 1$ $f(3) = 2$ So, the goal is to try and find a solution for f(n). I tried ...
1
vote
1answer
36 views

Help with recurrence equation

I need to solve the following recurrence equation $p_i =\begin{cases} r(p_{i-1}+p_{i+2}) &\mbox{if } i \text{ is odd} \\ (1-r)(p_{i-1}+p_{i}) & \mbox{if } i \text{ is even} \end{cases} i ...
0
votes
0answers
38 views

Solution to the recurrence relation with two equations

I am given : $$\begin{cases} v(0) = 0 \\ v(n)=\frac{1}{3}v(n+1)+\frac{2}{3}v(n-1)+1 & \text{ for } n < m\\ v(n)=k+v(1) & \text{ for } n \ge m\\ \end{cases}$$ The general solution to ...
6
votes
3answers
89 views

Please solve this recurrence relation question for $8a_na_{n+1}-16a_{n+1}+2a_n+5=0$

Suppose $a_1=1$ and $$8a_na_{n+1}-16a_{n+1}+2a_n+5=0,\forall n\geq1,$$Please help to sort out the general form of $a_n$. Here are the first a few values of the series. Not sure if they are useful as ...
4
votes
4answers
275 views

Explicit formula for a recursion

How can you express the following recursion explicitly? \begin{cases} T_0 = 1\\ T_n = 1 + 2\cdot T_{n-1}\\ \end{cases}
0
votes
1answer
20 views

Geometric recurrence, prove $g(k)=3g(k-1)-2g(k-2) is g(n)=2^n+1$

Geometric recurrence, prove gk = 3g(k-1) - 2g(k-2) is gn = 2n+1 using iteration. g1 = 3, g2 = 5 So, g3 = 3g(2) - 2g(1) = 3(5) - 2(3) = 9 <---- *which is 23+1 = 8+1 = 9 I'm unsure how to ...
0
votes
2answers
86 views

Integral of $\sin^n(x)$, recurrence relation, some properties

Practicing the manipulation of recurrence relations, I'm stuck on this : Defining $I(n)=\int_{0}^{\pi/2}sin^n(x)dx$, I got the recurrence relation $nI(n)=(n-1)I(n-2)$ for $n\ge2$. Now I'm also ...
1
vote
2answers
24 views

Not sure how to do Non-Homogeneous Recurrence Relations

I have a sample exam paper, and the answer is given, but I can't work out the answer from the question: Find the solution of: $a_n = \frac{1}{3}a_{n-1} + 2$ using $a_0 = 4$ Given Answer: $a_n = ...
1
vote
0answers
31 views

Solving a recurence system

Find a function $f(x,y) : \mathbb{N}^2 \to \mathbb{N}^2$ such that: $1 + f(x+1,y) - f(x,y) = a$ $1 + f(x, y+1) - f(x,y) = b$ $k + f(x-k, y) - f(x,y) = c \space \forall k \leq x$ $k + f(x,y-k) - ...
3
votes
1answer
56 views

2D Pattern in recursive digit sum of consecutive x^n

Take the recursive decimal digit sum of consecutive binary numbers $2^n$ as $n \to \infty$. You'll see something like this: n 2^n (recursive) sum of digits ...
0
votes
1answer
33 views

Solving Recurrence Relation Question

How do i solve recurrence relations like $a(n) = 3a(n/2) - 2a(n/4); a(1)=3; a(2)=5$? I don't think I can draw a recursion tree since there's no function like $2n$ at the end.
-1
votes
1answer
26 views

Understanding non homogeneous recurrence

Find a particular and then the general solution for the recurrence relation $a_n = 7\cdot a_{n−1} − 30 \cdot 2^n$ Trying to understand this equation.... We have been given a general formula for this ...
1
vote
3answers
49 views

Understanding a recurrence relation question.

A computer system considers a bit string a valid codeword if and only if it does not contain $3$ consecutive zeroes. Thus $010010$ is a valid codeword of length $6$ while $011000$ is not. Let $a_n$ be ...
0
votes
0answers
27 views

Second order, constant coefficient, homogeneous, linear difference equation

$a_n=x^2-5x+6=0$ So $x$ = $2$, $3$ Theorem $a_n=k_1 \alpha^n +k_2\beta^n $ Choice [1], I choose $2$ to be $\alpha$ and $3$ to be $\beta$ Then I get $a_n=A_1 2^n+A_23^n$ Choice [2], I choose $3$ to ...
1
vote
2answers
39 views

Recurrence with multiplication

Let $\{a_{n}\}$ be a sequence of nonnegative numbers such that $a_{n} = 2^{n}a_{n - 1}^{3/2}$. If $a_{1}$ is sufficiently small, why must $a_{n} \rightarrow 0$ as $n \rightarrow \infty$?
0
votes
1answer
45 views

How often does $p^k$ divide the Fibonacci numbers?

I would like to know about the Fibonacci numbers $F_n = 1,1,2,3,5,8, \dots$ in $\mathbb{Z}/p^k\mathbb{Z}$. $$ \mathbb{P}[p^k \text{ divides } F_n ] = \frac{\#\{1 \leq n\leq N: F_n \equiv 0 \mod ...
-2
votes
1answer
42 views

N balls of k colors on a cirlce, no two neighboring balls have same color - recursive algorithm

Suppose we have N balls of k different colors. What is the number of arrangements of these N balls on a circle with no two neighboring balls having the same color? Actually, the task is to make up a ...
2
votes
1answer
44 views

Recursive formula for creating a specific string

I have 5 characters ${a,b,c,1,2}$. $a_n$ is the number of strings I can create for $n$ length. I can't have the following sequences in a string: $a1$, $b2$ and any sequence of numbers $(12, 21)$. For ...
2
votes
3answers
35 views

Recursive integration

The integral I have is $$I_{n} = \int^{\pi/2}_{0} \cos^{2n+1}y \ \mathrm{d}y$$ And I have found $I_{n} = \frac{2n}{1+2n}I_{n-1}$ but I want to express $I_{n}$ in a form without $I_{n-1}$ how do I do ...
0
votes
2answers
45 views

Closed form for a strong recurrence relation

Let $\alpha_n$ be a sequence of complex numbers and consider the sequence $b_n$ defined by the (strong) recurrence relation : $$b_{n+1} = \sum_{k=0}^n \alpha_{n-k} b_k$$ with the initial condition ...
1
vote
1answer
47 views

Solving a (non-linear?) recurrence relation in 2 variables

I'm not sure if this problem is linear or not. Anyway, let me state the problem first: $$ \begin{align} P_n(a) &= \left(1 - \frac{a}{n} \times \frac{a-1}{n-1}\right) \times P_{n-1}(a) + ...
2
votes
3answers
91 views

Help with a proof that sequence of rational numbers $ a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$ converges to an irrational, $\sqrt2$

I know that there are sequences of rational numbers with irrational limits. One in particular I've seen is $$ a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$$ with $a_0 =1$, This is clearly rational ...