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

learn more… | top users | synonyms (2)

1
vote
0answers
17 views

Coefficients of the polynomials generated by $f_0=x,\ f_{i+1}=f_i\pm\dfrac1{f_i}$.

Let $f_0=x,\ f_{i+1}=f_i\pm\dfrac1{f_i}$ for $i\geq0$, i.e., $f_i=\dfrac{\sqrt{f_{i+1}^2\mp4}+f_{i+1}}2$ I have observed that $f_1=\dfrac{x^2\pm1}x$ $f_2=\dfrac{x^4\pm3x^2+1}{x(x^2\pm1)}$ ...
1
vote
2answers
16 views

Recurrence Relations Closed Form

So, the question is to derive the closed form solution to the recurrence relation $$T(n) = 3T(n-1) + 5,\hspace{5mm} T(0) = 0.$$ $\begin{align}T(n) &= 3T(n-1)+5 \\&= 3(3T(n-2)+5)+5 ...
1
vote
2answers
24 views

Solving a recuurence relation

How can I solve the following recurrence relation? $f(n+1)=f(n)+f(n-1)+f(n-2), \ f(0)=f(1)=f(2)=1.$ I can use the characteristic equation which is $x^3=x^2+x+1$. It has three distinct roots ...
0
votes
1answer
28 views

Combinatorial Proof of Identity b_n

Prove that: $$b_n = 1 + \sum\limits_{k=1}^{∞} \binom{n-1}{k}b_k.$$ Workings: The first thing I noticed is that the above equation looks very similar to a Bell Numbers proof: ...
2
votes
2answers
38 views

Generating function for Pell numbers

Problem: The Pell numbers $p_n$ are defined by the recurrence relation \begin{align*} p_{n+1} = 2p_n + p_{n-1} \end{align*} for $n \geq 1$. The initial conditions are $p_0 = 0$ and $p_1 = 1$. a) ...
0
votes
0answers
13 views

Proving a Recurrence Using Substitution

I am trying to understand an example of solving a recurrence using substitution (or unrolling it) in my book right now, but all of the steps do not seem clear to me. Here is the basic example: ...
1
vote
0answers
36 views

Help Solve Recurrence Relation T(n) = 3T(n/2) + O(n)

Given recurrence $$T(n) = 3T(n/2) + O(n)$$ $$let\:cn >= O(n)$$ for some constant c I can bound $$T(n)$$ in terms of $$T(n/2)$$ so I have $$T(n) <= 3T(n/2)+cn, \ \ \ \ \ k = 1 \ call$$ So I ...
1
vote
2answers
37 views

Induction proof concerning Pell numbers

Problem: The Pell numbers $p_n$ are defined by the recurrence relation \begin{align*} p_{n+1} = 2p_n + p_{n-1} \end{align*} for $n \geq 1$, together with $p_0 = 0$ and $p_1 = 1$. Prove with ...
0
votes
1answer
8 views

Problem with finding generating function for a sequence

Problem: Determine the generating function for the sequence $(a_k)$ given by $a_0 = 2$ and $a_k = 3a_{k-1} - 4$ for $k \geq 1$. Solution: We define $f(x) = \sum_{k=0}^{\infty} a_k x^k$ for the ...
2
votes
0answers
12 views

Need help in understanding the procedure of expanding recurrence formula

So here is the actual expansion: \begin{align} T(n) &= T(n-1) + n \\ &= T(n-2) + (n-1) + n \\ &= T(n-3) + (n-2) + (n-1) + n \\ &\vdots \\ &= T(0) + 1 + 2 + \ldots + (n-2) + (n-1) ...
0
votes
0answers
16 views

Explicit formula of f(n+1) = f(n) + k*(M - f(n))*(f(n) - m)

I have a lot of difficulty trying to translate the worked examples of generating functions I see online because they all use first order terms. That said, I would like to know how to approach ...
-1
votes
0answers
11 views

A great recursive to solve with application in bioinformatics

How could I solve this recursive equation? $$N[i,j]=N[i-1,j]+a.N[i,j-1]-b.N[i-1,j-1]$$ where: $$\begin{array}{ll} a=(4^i-1)/4^i\\ b=(4^i-4)/4^i\\ N[0,j]=1 &, j>=1\\ N[i,0]=0 &, i>=0\\ ...
-5
votes
1answer
18 views

is there constant $k$ such that nth fibonnaci number $F_n$ satisfies $F_n > k2^n$ and vice versa? [on hold]

Is there constant $k$ such that nth fibonnaci number $F_n$ satisfies $F_n > k2^n$? Also is there constant $k$ that $k2^n>F_n$?
0
votes
0answers
13 views

How to calculate recurrence $F(n) = F(n/u) + \Theta(n^k)$ where $u,k \in \mathbb{N}$

$\Theta$ is used as in Bachmann-Landau notation (often called as Big-O notation convention). How does one in general the recurrence relation of the following from: $$F(n) = F(n/u) + \Theta(n^k) ...
2
votes
0answers
30 views

Why do I generally see real solutions to recurrence relations?

I haven't worked very much with recurrence relations, but for the ones I have worked with I always get real solutions, which is strange to me because looking briefly at the procedure for solving ...
-1
votes
0answers
22 views

Solving recurrence relation with $f(2n)$ and $f(2n+1)$ [duplicate]

Looking to figure out the recurrence relation for the following: $f(0)=1$ $f(1)=1$ $f(2)=2$ $f(2n)= f(n) + f(n + 1) + n\quad (\text{for } n > 1)$ $f(2n + 1) = f(n - 1) + f(n) + 1\quad (\text{for ...
0
votes
1answer
38 views

How do I solve this recurrence? [on hold]

I want to find the recurrence equation of $$\begin{align} f(n+1)-f(n) &= -n+3\cdot 2^{n-1}-1\\ f(1) & = 4 \\ f(2) & = 5 \end{align}$$ (original scan) Any ideas?
1
vote
1answer
48 views

Recurrence equation solution?

Can you help me with the solution of this recurrence equation? $$ f(n+2) = -2f(n) +3f(n+1) +n \quad\mid\quad f(1)=4 \quad\mid\quad f(2)=5 $$ Thank you.
1
vote
2answers
38 views

general solution of $y(n+2)+2y(n+1)-3y(n) = -2n$

I would like to find the general solution of $y(n+2)+2y(n+1)-3y(n) = -2n$. I've found the general solution of $\tilde{y}(n+2)+2\tilde{y}(n+1)-3\tilde{y}(n) = 0$ to be $\tilde{y}(n) = c_1(-3)^n+c_2$. ...
3
votes
0answers
21 views

Solve recurrence relation merge sort

I'd like to know how I can solve a recurrence relation like the one from merge sort. I know how to solve recurrence equations that start with $a(n)=a(n-1)+(n-1)$, but I don't know how to solve ...
0
votes
1answer
29 views

How to solve the recursion $f(n+2)=3f(n+1)-2f(n)+5$?

$$f(n+2)=3f(n+1)-2f(n)+5, \text{ with } f(1)=4, f(2)=5\\ f(n+2)=3f(n+1)-2f(n)+n, \text{ with } f(1)=4, f(2)=5$$ I can't find anywhere the solution for sequences of this type and am unable to figure ...
18
votes
1answer
3k views

Connection between the Laplace transform and generating functions

As I was sitting through a boring lecture rehashing basic techniques to solve ordinary differential equations, I began thinking about the Laplace transform and scribbled down a few ideas that I've ...
-2
votes
1answer
24 views

Recurrence relations and initial conditions [closed]

I couldn't figure out how to do the super/subscript, hence the photo.
2
votes
2answers
22 views

Determining order class of $T(n) = nT(n-1) + n$ with $T(1) = 1$

I'm trying to solve the following problem: Define $T(n) = n\cdot T(n-1) + n$ with $T(1) = 1$. Is $T(n) \in \mathcal O(2^n)$? I started by finding the time complexity of $T(n) = n\cdot T(n-1) + ...
-2
votes
0answers
22 views

Recurrence relation -unique question? [closed]

How to solution please? Thanks…^^
1
vote
1answer
31 views

Solving recurrences using generating functions

I have the following solution for solving a recurrence using a generating function and I have a question on why it is multiplied by (1-z) and why this causes the second summand to disappear.
0
votes
1answer
21 views

Two recurrence relations gcd proof

Let $q_1, q_2,\ldots$ be a sequence of integers with $q_i\gt0$ for all $i\gt 1$. Define $(a_n)_{n\ge-1}$ and $(b_n)_{n\ge-1}$ by the following recurrence relations: $a_{-1}=0,\ a_0=1,\ b_{-1}=1,\ ...
1
vote
2answers
32 views

the general solution of $y(n+3)-\frac{2}{3}y(n+1)+\frac{1}{3}y(n) = 0$

I have some trouble finding the correct solution for the difference equation $$y(n+3)-\frac{2}{3}y(n+1)+\frac{1}{3}y(n) = 0$$ I've found that the characteristic equation of the difference equation ...
1
vote
1answer
50 views

What Did I Do Wrong When Solving For This 2nd Order Differential Equation? (answered myself)

$$ \frac{y''}{y'}+y' = f(x) $$ I set the following to be true: $$ y = \sum_{n=0}^{\infty} a_n x^n $$ $$ f(x) = \sum_{n=0}^{\infty} b_nx^n $$ Therefore: $$ y'' = y'(f(x)-y') $$ $$ ...
7
votes
2answers
71 views

Closed form of a recursive relation

A sequence $\langle a_n\rangle$ is defined recursively by $a_1=0$, $a_2=1$ and for $n\ge 3$, $$a_n=\frac 12 na_{n-1}+\frac 12n(n-1)a_{n-2}+(-1)^n\left(1-\frac n2\right).$$ Find a closed form ...
4
votes
3answers
101 views

Prove that $1\cdot f(1)+ 2\cdot f(2)+ …+ n\cdot f(n) \leq n(n+1)(2n+1)/6$ where $f(n+1) = f(f(n))+1$

Consider checking function $\mathbb{N}\to \mathbb{N}$ relationship $f(n+1) = f(f(n))+1$, for any positive integer $n$. Prove that $1\cdot f(1)+ 2\cdot f(2)+ ...+ n\cdot f(n) \leq n(n+1)(2n+1)/6$ for ...
2
votes
3answers
53 views

Prove that {$r_n$} satisfies $r_n = 7r_{n-1} - 10r_{n-2}, n \geq 2$

Problem: For the sequence $r$ defined by $$r_n = 3 \cdot 2^n - 4 \cdot 5^n, \ \ \ n \geq 0$$ Prove that {$r_n$} satisfies $$r_n = 7r_{n-1} - 10r_{n-2}, \ \ \ n \geq 2$$ Can this problem be ...
0
votes
0answers
33 views

Solving a recurrence relation using the substitution method

Consider the recursive function $f(n)=3f(n/4)+2n $, $f(16)=32.$ Where n is always a power of 4 greater than 16. We must find a closed form utilizing substitutions. So, after one substitution, f(n) ...
2
votes
2answers
23 views

How to solve the recurrence relation $t_n=(1+c q^{n-1})p~t_{n-1}+a +nbq$?

How to solve $$t_n=(1+c q^{n-1})p~t_{n-1}+a +nbq,\quad n\ge 2.$$ given that $$t_1=b+(1+c~p)(a~q^{-1}+b),\qquad p+q=1.$$ N.B- Some misprints in the question I corrected. Sorry for the misprint $an+b$ ...
0
votes
1answer
23 views

Computing time-complexity of DP recursion

I've written an algorithm which uses 3-dimensional DP table and it goes as follows: $DP[i][j][0]$ can be computed in $O(1)$ for any $i,j$ and $DP[i][j][k]=\max(DP[i][m][0]+DP[m+1][j][k-1]) $ for all ...
0
votes
0answers
32 views

Stability proof of the difference equation $y(n+2)-y(n) = 0$

I'd like to be able to prove that the solutions of the following equation $y(n+2)-y(n) = 0$ are stable, but I'm having trouble defining a correct $\delta(\epsilon)$ such that the stability condition ...
1
vote
1answer
39 views

recurrence relation with variable coefficients

How to solve recurrence relation $y(n)= y(n-1)+ (n-1)y(n-2)$ where $n$ is a variable ? $y(n)$ is a $n$th term, $y(n-1)$ is $(n-1)$th term and $y(n-2)$ is $(n-2)$th term.
0
votes
1answer
31 views

Can someone check my answers to this problem?

This is from Discrete Mathematics and its Applications Definition of recurrence relation from book From my understanding, compounded annually means that every year(annually) the account will ...
3
votes
0answers
105 views

Simplification of recursive polynomials

Suppose I have known polynomials $p_i, i=0\ldots k-1$. I have the following horrific looking recursive equation: ...
0
votes
1answer
101 views

Show that the following recurrence relation satisfies the inequality $\displaystyle f(1) + 2f(2) + \cdots + nf(n) \le \frac{n(n+1)(2n+1)}{6}$

Consider the functions $f:N^*→N^*$ satisfying relation $f(n+1)=f(f(n))+1$ for any positive integer $n$, a) Demonstrate that $\displaystyle f(1) + 2f(2) + \cdots + nf(n) \le \frac{n(n+1)(2n+1)}{6}$, ...
3
votes
4answers
81 views

Solving Linear Recurrence Relationship of Two Variables

How to solve a recurrence equation like this: $(a_{n+1},b_{n+1})=(3a_n+5b_n,a_n+3b_n)$ with the initial condition: $(a_1,b_1)=(3,1)$ The only way I can think of to solve an equation like this is ...
0
votes
0answers
25 views

Homogeneous system of linear equations with structure

I have a homogeneous system of linear equations $Ax = 0$. The matrix $A$ is of size $N$. For $\det(A) = 0$, the rank of the matrix $A$ is $N - 1$. I am interested in the case $\det(A) = 0$ and want to ...
2
votes
1answer
60 views

Solve recursion relation

Let $E$ be a real number. Consider the following recurrence relation: \begin{equation} a_{n+2} (n+3)(n+2) + a_{n+1} + E a_n = 0 \end{equation} subject to $a_0 = 1$ and $a_1 = -1/2$. By using the ...
0
votes
1answer
64 views

Mathematical induction

The sequence of real numbers $a_1, a_2, a_3,...$ is such that $a_1=1$ and $$a_{n+1}=\left(a_n+\frac1{a_n}\right)^\lambda,$$ where $\lambda$ is a constant greater than $1$. Prove by mathematical ...
2
votes
1answer
46 views

Recurrence relation-there is no initial condition

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: ...
1
vote
3answers
20 views

Working on sequence, possibly recursive

I am working on this problem which asks to find if the sequence converges or not and if so the value it converges to. I am not sure how to deal with this type of question, but I feel like it may be a ...
31
votes
6answers
5k views

Proof the Fibonacci numbers are not a polynomial.

I was asked a while ago to prove there is no polynomial $P$ in $\mathbb R$ such that $P(i)=f_i$ for all $i\geq0$. I tried to get a proof as slick as possible and here's what I got. Let ...
4
votes
3answers
101 views

To show sequence $a_{n+1}= \frac{a_n^2+1}{2 (a_n+1)}$ is convergent

Let $a_1=0$ and $$a_{n+1}= \dfrac{a_n^2+1}{2 (a_n+1)}$$ $\forall n> 1.$ Show that sequence $a_n$ convergent. I tried to prove $a_n$ is less than 1 by looking at few terms. But i failed to prove ...
3
votes
0answers
63 views

Duration of a Gambler's Ruin game against an opponent with infinite credit

A gambler enters the casino with $x\$$ in his pocket and sits on some table. At each iteration he bets $1\$$ and either wins $1\$$ with probability $p\leq\frac{1}{2}$ or loses $1\$$. Assuming that ...
1
vote
1answer
45 views

Legendre Series Recurrence Relation Divergence at $x=\pm1$, using Gauss test

How to show that the Legendre Series solution $y_{even}$ and $y_{odd}$, diverges as $x = \pm1 $. $y_{even} = \sum_{j=0,2,\ldots}^\infty a_jx^j$, where $a_{j+2}=\frac{j(j+1)-n(n+1)}{(j+1)(j+2)}a_j$. ...