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

learn more… | top users | synonyms (2)

4
votes
1answer
172 views

Solve the recurrence: $f(n, k) = f(n-1, k-1) + f(n-1, k) + 2^n$

This is somewhat like Pascal's triangle but with an additional $2^n$: $$\left\{\begin{align*} &f(n,0)=f(n,n)=2^n-1\\ &f(n,k)=f(n-1,k-1)+f(n-1,k)+2^n \end{align*}\right.$$ Is there a direct ...
4
votes
1answer
134 views

Resource on Infinite Systems of Difference Equations

In my efforts (somewhere on the boundary of discrete mathematics and theoretical computer science), I have come upon the necessity of solving (or at least finding out some of the solution's ...
1
vote
0answers
69 views

Deriving this recursive expression for Riemann Prime Counting Function?

Why does this work? $f(n,k,1)=0$ $f(n,k,j)= \frac{1}{k} - f(\lfloor\frac{n}{j}\rfloor, k+1, \lfloor\frac{n}{j}\rfloor) + f(n,k,j-1)$ Here, f(n,1,n) computes the Riemann Prime Counting Function. ...
3
votes
1answer
64 views

Recursively Defined Entities

So I am having some trouble understanding how one is to come up with the recursive definition to the following problem... We are given a rectangle of width $2$ and length $n$. Suppose we have ...
1
vote
1answer
65 views

How do I solve the following difference differential equation

While studying a particular physical system, I arrived at the following difference differential equation: $$\frac{dx_n(t)}{dt} = -g \left\{\sqrt{(n + 1)(n + 2)}x_{n+1}(t) - (2n +1)x_n(t)\right\},$$ ...
1
vote
1answer
64 views

Sequence Function?

Problem: What is the close-form/ recursive equation/ generating fucntion of the following sequence, which has following 256 entries: 1 7 7 7 7 9 9 9 7 9 9 9 7 9 9 9 7 11 11 11 11 13 13 13 11 13 13 ...
0
votes
1answer
242 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 ...
9
votes
1answer
361 views

Closed form for $a_{n+1} = (a_n)^2+\frac{1}{4}$

I've been given the following sequence: \begin{align*} &a_0 = 0; \\ &a_{n+1} = (a_n)^2+\frac{1}{4}. \end{align*} I also have to prove that whatever I come up with is correct, but that will ...
1
vote
3answers
135 views

Using complete induction, prove that if $a_1=2$, $a_2=4$, and $a_{n+2}=5a_{n+1}-6a_n$, then $a_n=2^n$

Could anyone please explain to me how to do this problem by using the principle of complete induction? Thanks. :) Let $a_1=2$, $a_2=4$, and $a_{n+2}=5a_{n+1}-6a_n$ for all $n\geq 1$. Prove that ...
6
votes
1answer
131 views

How find $a_{n}$ if $a_{n+1}=\sqrt{2a_n+1}$

let $a_{1}=\dfrac{\sqrt{2}}{4}$ and such $$a_{n+1}=\sqrt{2a_{n}+1}$$ find $a_{n}$ my idea:let $a_{n}=\dfrac{1}{2}\cos{x_{n}}$ $$\Longrightarrow ...
3
votes
3answers
529 views

Number of Regions in the Plane defined by $n$ Zig-Zag Lines

Fellows of Math.SE, I have been scratching my head at a solution to an exercise in Donald Knuth's Concrete Math. Here is the problem: Here is the solution (I hid it in case someone wants to solve ...
1
vote
2answers
122 views

Recurrence relation: $x_{n+1} = \frac 12 x_n + \frac 1 {x_n},$ [duplicate]

$$x_{n+1} = \frac 12 x_n + \frac 1 {x_n}, x_0 \neq 0$$ $$ a = \frac a2 + \frac 1a \Rightarrow a = \frac {a^2 + 2} {2a} \Rightarrow 2a^2 = a^2 + 2 \Rightarrow a^2 = 2 \Rightarrow a = \pm \sqrt 2$$ If ...
2
votes
1answer
103 views

solution of difference equation

I am trying to solve the following difference equation: ...
0
votes
3answers
147 views

Recurrence relation with periodic function

$$x_{n+1} = x_n + \sin x_n$$ $$x_{n+1} = \sin \left(\frac {\pi} {2} x_n\right)$$ How to solve these? Or, at least, what can be said about thier behavior and limits?
0
votes
1answer
34 views

How to obtain generating function and an analytic solution

I have the following recurrence relation, and I need to obtain generating function and an analytic solution. How to go about with it? $$ f(N,M) = 0, N < M\\ f(N+1,M+1) = 2f(N,M) + (N-1)f(N,M+1), N ...
1
vote
5answers
87 views

solution of recurrence relation $x_{n+1} = \frac {1}{x_n + 1}$

$$x_{n+1} = \frac {1}{x_n + 1}; x_1 > 0$$ How to transform it into the form $x_n = $? I need the solution in order to check if it converges at any $x_1 > 0$.
1
vote
3answers
80 views

solution of recurrence relation

I need help in solving recurrence relation: $$x_{n+1} = \exp (-x_n) + 2; x_1 = 1$$ I suppose that I should, assuming the limit exists, solve: $a=e^{-a} + 2$. But how?
2
votes
1answer
62 views

How to solve $x_{n+1} = \frac{x^2_n + 1}{x_n}$ if $x_0>1$?

How to solve the following recurrence relation, assuming that $x_0 > 1$: $$x_{n+1} = \frac{x^2_n + 1}{x_n}$$ Am I allowed to divide the fraction, that is $x_{n+1} = x_n + \frac{1}{x_n}$?
1
vote
4answers
85 views

Non-homogenous recurrence relation

I need to solve the recurrence relation $A(n)=2A(n-2)+ 2^{n-2}$. I tried writing out equations up to the $A(2)$ and multiplying by powers of two and adding all the equations together then all the ...
0
votes
2answers
75 views

recurrence relation: $x_{n+1} = x^2_n - 2x_n + 2$

$$x_0 = \frac32; x_{n+1} = x^2_n - 2x_n + 2$$ $$\Rightarrow x = x^2 - 2x +2 \Rightarrow x^2 - 3x +2 = 0 \Rightarrow x = {1;2} $$ How to determine which one is the limit, i.e. $\lim_{n\rightarrow ...
2
votes
1answer
148 views

Recurrence relation in complex domain

I am bumping in the following problem : the expansion of $$x^{i/k} \operatorname{LerchPhi}[x,1,i/k]$$ leads, for each value of i, to a linear combination of k terms, each of them writing $$a(j) ...
3
votes
1answer
87 views

Solution to $u_{n+1}=u_n/n+u_{n-1}/(n-1)$

What is the solution to the following recurrence relation $$u_{n+1}=\frac{u_n}{n}+\frac{u_{n-1}}{n-1}\ \forall n\geq 2$$ where $u_2=u_1=1$?
1
vote
0answers
54 views

Simplification of differential equation when definition interval becomes small?

Assuming the following differential equation on the interval $0<x<c$ with a rational function $f(x,c)$ $$\left(\frac{d^2}{dx^2}+f(x,c)\right)y(x,c)=0,$$ what kind of simplifications (if any) ...
0
votes
1answer
50 views

recurrence relation question

How can I build a recurrence equation if there isn't an $n$-variable? Example: $a_n = 3$. Also, how would I start making a recurrence equation for $a_n = 2n + 3$?
1
vote
0answers
102 views

Scaling for characteristic polynomial of sequence of growing matrices

This is a follow-up question to Limit of sequence of growing matrices. There I was considering a sequence of matrices defined by $$ K_L = \left[H\otimes I_{2^{L-2}}\right]\left[I_2 \otimes ...
1
vote
1answer
57 views

Solution to the recursive relation $l_{n}=b_{n-1}+\sum_{k=0}^n l_n a_n b_{n-k} $

I have the following recursive equation $$l_{n}=b_{n-1}+\sum_{k=0}^n l_k a_k b_{n-k},\ n\geq 1$$ where $b_n=1/n!,\ a_n=S_n(-1)$ where $S_n(x)=\sum_{k=0}^n \frac{x^k}{k!}\ \forall x\in \mathbb{R}$ and ...
1
vote
1answer
55 views

Prove by induction that $d_n=2^n+3^n$, where $d_n = 5d_{n-1}-6d_{n-2}$

I have one more induction question. $d_0 =2 $ $d_1=5$ let $d_n=5d_{n-1} - 6d_{n-2}$ Prove that $d_n=2^n+3^n$
0
votes
2answers
358 views

Recurrence relations and generating functions question

Let $A_n$ be the set of different paving of a $2\times n$ using $2\times 1$ or $1 \times 2$ tiles. We'll define $a_n$=$|A_n|$. 1] Find recurrence relation: I found it -> $a_n=a_{n-1}+a_{n-2}$ with ...
0
votes
3answers
91 views

Fiddling with a Fibonacci-Like Sequence

Let $X\in\mathbb{Z}.$ Let $F_n$ be a sequence of positive integers given by $$F_{i+1}=F_i+F_{i-1}$$ $$F_2=X*F_1+F_0$$ I am trying to find an upper bound or (sharp) inequality of $F_i$ in terms of ...
7
votes
1answer
308 views

How prove that $x_1 = x_{2000}$ implies $x_2 \ne x_{1999}$, where $x_{n+2}=\frac{x_{n}x_{n+1}+5x^4_{n}}{x_{n}-x_{n+1}}$?

Let $x_{1},x_{2},\cdots$ be real numbers, such that for $n \ge 1$: $$x_{n+2}=\dfrac{x_{n}x_{n+1}+5x^4_{n}}{x_{n}-x_{n+1}}$$ If $x_{1}=x_{2000}$, prove that $x_{2}\neq x_{1999}$. my idea ...
2
votes
1answer
154 views

How to find periodic solutions using a graphing calculator

We have the model $X_{n+1} = 4\left(X_n - \dfrac{1}{2}\right)^2$ with a given $X_0$ on the domain $[0,1]$. We have the following question: Use your graphing calculator to figure out if there are ...
2
votes
1answer
68 views

An inequality property of the Fibonacci sequence

Given the Fibonacci sequence $F_n$, Wikipedia says (http://en.wikipedia.org/wiki/Fibonacci_number#List_of_Fibonacci_numbers) $$ F_{2n-1} = F_n^2+F^2 _{n-1}$$ so that $$F_{2n-1}>F^2_n$$ What is the ...
-2
votes
1answer
1k views

Solve: $T(n) = T(n-1) +(1/n)$ by iteration

Use iteration method to solve: $1.$ $T(n) = T(n-1) + \frac{1}{n},\,(T(0)=1)$ $ 2.$ $T(n) = 3T\left(\dfrac{n}{3}\right) +1,\,(T(3)=1)$
1
vote
1answer
40 views

Simplifying a Recurrence Relation

$(n_i) $ is a sequence of integers satisfying $n_{i+1}=a_{i+1}n_i+n_{i-2}$. Consider a subsequence $(n_{i_j}).$ Can $n_{j_{i+1}}$ be written in terms of $n_{j_i}$? An attempt is to use the recurrence ...
1
vote
1answer
59 views

Find a recursive formula for the following problem

Let $a_n$ be the number of bricks in a path that is $n \geq 1$ long. We have 3 types of bricks: Blue: $2$ cm long Red: $3$ cm long Green: $1$ cm long When a blue brick can't be placed next to a ...
1
vote
2answers
64 views

Recursion problem help

The following are the teachers example problems. The issue is that I don't understand the exact steps they took to go from $f(0)$ to $f(1)$ to $f(2)$ to $f(3)$. What I'm asking here is if someone ...
1
vote
2answers
2k views

Solving non homogeneous recurrence relation

I am having a hard time understanding these questions. I know I need to find the associated homogeneous recurrence relation first, then its characteristic equation. I cant figure out how to find the ...
1
vote
1answer
207 views

Using partial fractions to find explicit formulae for coefficients?

The set of binary string whose integer representations are multiples of 3 have the generating function $$\Phi_S(x)={1-x-x^2 \over 1-x-2x^2}$$ Let $a_n=[x^n]\Phi_s(x)$ represent the number of strings ...
1
vote
2answers
105 views

Solve non-homogeneous linear recurrence

I have the following recurrence $$a_n - 3a_{n-2} + 2a_{n-3} = 9 (-2)^n$$ with initial conditions $a_0 = 0, a_1 = 1, a_2 = 26$. I wish to find an explicit formula for $a_n$. The characteristic ...
2
votes
2answers
41 views

adding infinitely many equations side by side in a recurrence relation

we are given that $x+\beta y_{n+1}=k_n+y_n$ for all $n\in\mathbb{N}\cup\{0\}$, where $\beta\in(0,1)$, $y_0=0$, and $k_n$ is 6 whenever $n$ is even and 4 whenever odd. Being the naive mathematician I ...
1
vote
2answers
35 views

Fixed points for $k_{t+1}=\sqrt{k_t}-\frac{k_t}{2}$

For the difference equation $k_{t+1}=\sqrt{k_t}-\frac{k_t}{2}$ one has to find all "fixed points" and determine whether they are locally or globally asymptotically stable. Now I'm not quite sure ...
2
votes
3answers
629 views

Number of sequences with n digits, even number of 1's

ASKED: Let $c_n$ be the number of sequences with $n$ digits from $\{1,2,3,4\} $ with an even number of $1's$. Determine $c_n$ for $n \geq 0$. GIVEN RESULT: $c_{n+1} = 3 \cdot c_n + 1 \cdot ...
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 : ...
1
vote
2answers
235 views

Simplify a recursively defined function in Maple

I have the following problem. Out of the runtime analysis of an divide and conquer algorithm I got the following formula for the necessary flops: ...
2
votes
1answer
62 views

How to evaluate $\lim_{n \to \infty}{\frac{a_1 \cdot a_2\cdot a_3 \ldots a_{n}}{a_{n+1}}}$, given $a_{n+1} = a_{n}^{2} -1,a_1 = \sqrt{5}$?

Let $a_{n+1} = a_{n}^{2} -1,a_1 = \sqrt{5}.$ How would one evaluate $$\lim_{n \to \infty}{\frac{a_1 \cdot a_2\cdot a_3 \ldots a_{n}}{a_{n+1}}}?$$ Added: Someone else asked me this question today, ...
3
votes
1answer
69 views

Asymptotics of a Recursively defined sequence

Suppose we define the sequence $a_n$ recursively by $p_1=1/2, a_1=2$, $p_{n+1}=p_n-\frac{{p_n}^2}{a_np_n+1}, a_{n+1}=a_n+\frac{1}{p_n}$. How does $(a_n)$ behave for large $n$? For instance, what is a ...
1
vote
1answer
356 views

numerically evaluate a continued fraction

I am looking at a continued fraction of the form $$ F_n = \cfrac{1}{1+\cfrac{p_1}{1+\cfrac{p_2}{1+\cfrac{p_3}{1+\ldots}}}} $$ where $p_n$ is a function I know. For simplicity I just take it to $p_n=n$ ...
3
votes
0answers
96 views

What is this bifurcation?

I have a discrete dynamical System $x_{n+1}=f(x_{n},x_{n-1},x_{n-2},x_{n-3},x_{n-4},\lambda)$ with a paramteter $\lambda>0$, and where all $x_{n}$s are in [0,1]. $f$ is actually a larger ...
2
votes
3answers
266 views

Closed Form of Recurrence Relation

I have a recurrence relation defined as: $$f(k)=\frac{[f(k-1)]^2}{f(k-2)}$$ Wolfram Alpha shows that the closed form for this relation is: $$ f(k)=\exp{(c_2k+c_1)} $$ I'm not really sure how to go ...
1
vote
1answer
146 views

Help with a different approach to extracting a polynomial equation from differences

It is well known that we can determine the degree of a polynomial can be found by finding when the differences are the same. i.e. if the second differences are the same, it is a polynomial of the 2nd ...