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

learn more… | top users | synonyms (2)

0
votes
0answers
15 views

Help finalizing a recurrence relation

(Yes this is homework) 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, \ \ \ \ \ ...
-5
votes
1answer
15 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
9 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
27 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
34 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 ...
14
votes
0answers
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
23 views

Recurrence relations and initial conditions [on hold]

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

Recurrence relation -unique question? [on hold]

How to solution please? Thanks…^^
1
vote
1answer
30 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
30 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
99 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
32 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$ ...
-1
votes
1answer
36 views

$t(n) = t(n-2) + 2^n$ [closed]

Assume that $t(n) = 1$ for $n\le 1$ and the recurrence given is for $n > 1$ $$t(n) = t(n-2) + 2^n$$ trying to find the recurrence within big theta accuracy, help!
0
votes
1answer
20 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
31 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 ...
-4
votes
1answer
23 views

closed form of recurrence relations [closed]

How to find closed form of these recurrence relations : 1. $a_n = 2a_{\frac{n}{2}} + \log_2 n ;\; n= 2^k, k \geq 1, a_1 = 1$ 2. $a_n ^3 = 2a^3_{n-1} + 1 ; \; n \geq 2, a_1 = 1$ 3. $a_n + na_{n-1} = ...
1
vote
1answer
38 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
30 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
80 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
63 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 ...
3
votes
3answers
99 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
44 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$. ...
0
votes
1answer
12 views

Laguerre Recursion Relation from two other recurrence relation

How to show this, $$xL_n'(x) = nL_n(x)-nL_{n-1}(x)$$ Laguerre recursion relation from these two recursion relations, $$L'_{n+1}(x)-L'_n(x)+L_n(x)=0\\(n+1)L_{n+1}(x)-(2n+1-x)L_n(x)+nL_{n-1}(x)=0$$ ...
5
votes
1answer
108 views

What is the expected number of questions answered to complete a sequence in which wrong answers send you to the start?

Given a sequence of n questions that each contain x answer choices, what is the expected number of questions answered before answering all questions correctly if answering a question incorrectly sends ...
3
votes
1answer
46 views

Recurrence relation of number of groups of matching parenthesis

I was trying to solve this problem: How many ways can N pairs of parenthesis form K matching groups? By 'a group of matching parenthesis' I mean a sequence of matching parenthesis which can not be ...
0
votes
0answers
47 views

Find a big-O estimate for $f(n)=2f(\sqrt{n})+1$

Is the answer from the below linked question correct for my question? Or does the differing of $+ \log(n)$ instead of $+1$ change the outcome of the master theorem? Similar question here
19
votes
6answers
263 views

Why does every “fibonacci like” series converge to $\phi$?

It's is well known that the ratio of side-by-side fibonacci numbers converge to $\phi$. But it seems by my calculations, that if one starts with any pair of numbers one will also get a ratio that ...
2
votes
0answers
45 views

What techniques does Mathematica use to find solutions to these sequences?

This question is related to my previous question: Need help finding a closed form for complicated sum. An answer to that question led my to try and find the general term of the following recurrence: ...
1
vote
1answer
87 views

Asymptotic behaviour of a recurrence relation - How to solve

I'm going over a chapter in recurrence relations in preparation for job interviews and came across the following. I'd like to gain some better understanding of how to solve such a question. Find a ...
1
vote
1answer
34 views

Rewrite formula using exponential generating functions

In the equation below I want to extract $b_k$. $$\frac{a_n}{n!} = \sum_{k=0}^{n}\frac{b_k}{k!(n-k)!}$$ For all other exercises in the book I had to use $e^x = \sum_{n=0}^{\infty}\frac{x^n}{n!}$ or ...
0
votes
1answer
20 views

Recursive equation for non-recurisve equation.

Determine recursive equation for: ( $A$ is any const) $a_n = An!$ I am asking for any advice.
1
vote
2answers
31 views

System of recursive equation.

Let's consider: $$u_o = -1, v_0 = 3$$ $$\begin{cases} u_{n+1} = u_n + v_n \\ v_{n+1} = -u_n + 3v_n \end{cases}$$ I tried: $$x^n = u_n , y^n = v_n$$ $$\begin{cases} x^{n+1} = x^n + y^n \\ y^{n+1} = ...