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

learn more… | top users | synonyms (2)

1
vote
2answers
50 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
14 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
16 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
22 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 ...
0
votes
0answers
17 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
34 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
vote
1answer
53 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
43 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
39 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
34 views

Solving recurrence relations using master's theorem

Can we solve following recurrence relation using Master's theorem- $T(n)=T(n/2)+\log n$ The thing to notice here is that, do $n (n^{\log b} a)$ and $\log n (f(n))$ have an exponential ...
0
votes
1answer
33 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 ...
20
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
2answers
70 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) + ...
1
vote
1answer
51 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
32 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
33 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
54 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') $$ $$ ...
8
votes
2answers
85 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
103 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
54 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
43 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
3answers
103 views

Prove by induction that $G(n)=2^n$

I have a task to solve with algorithm, which is writing all the binary numbers. I wrote the recurrence relation below, as I count the few first values: $$G(n) = \begin{cases}1&\qquad n = 0\\ 2G(n ...
2
votes
2answers
28 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
34 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
38 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
81 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
112 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
106 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
189 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
46 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
81 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
67 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
81 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
25 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 ...
32
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
109 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 ...
4
votes
1answer
89 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
68 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
25 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
152 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
75 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
71 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
20
votes
6answers
481 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
50 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
122 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
39 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
23 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
33 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} = ...
1
vote
3answers
60 views

To prove $x_n<3$ for sequence $x_{n+1} = \frac{12(1+x_n)}{13+x_n}$ by induction

Prove $x_n<3$ for a sequence given by $$x_{n+1} = \frac{12(1+x_{n})}{13+x_{n}}$$ where $x_1$ is positive real number less than $3$. For $n = 1$ statement is trivial, but I am stuck at doing ...