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

learn more… | top users | synonyms (2)

0
votes
1answer
7 views

Derivative of a second-iterate map

I have a homework problem I'm working on about the discrete logistic equation: $f(x)=rx(1-x)$ So far, through some experimentation and polynomial division I've dtermined that the fixed poits of ...
1
vote
2answers
23 views

Prove that a recurrence relation (containing two recurrences) equals a given closed-form formula.

Prove that $a_n = 3a_{n-1} - 2a_{n-2} = 2^n + 1$ , for all $n \in \mathbb{N}$ , and $a_1 = 3$ , $a_2 = 5$ , and $n \geq 3$ Basis: $a_1 = 2^1 + 1 = 2 + 1 = 3$ $\checkmark$ $a_2 = 2^2 + 1 = 4 + 1 = 5$ ...
0
votes
4answers
2k views

Converting an explicitly defined function to a recursive one

In studying for an exam, I had difficulty with these two questions: Give a recursive form (including bases) for the following functions. $$f(n) = 5 + (-1)^n$$ $$f(n) = n(n+3)$$
6
votes
3answers
310 views

Repertoire method for solving recursions

I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics: \[ g(1)=\alpha \] \[ g(2n+j)=3g(n)+\gamma n+\beta_j \] \[ \mbox{for}\ j=0,1\ \mbox{and}\ n\geq1 \] I ...
2
votes
5answers
4k views

Solve the recurrence $T(n) = 2T(n-1) + n$

Solve the recurrence $T(n) = 2T(n-1) + n$ where $T(1) = 1$ and $n\ge 2$. The final answer is $2^{n+1}-n-2$ Can anyone arrive at the solution?
2
votes
1answer
27 views

Solve the recurrence $T(n) = 2T(n-1) + n, T(1)=1, n\geq 2$

This question has been already solved here, I just want to figure out why I'm not being able to solve it using my method. Here's what I did - $T(n)=2T(n-1)+n$ $T(n-1)=2T(n-2)+(n-1)$ $\therefore ...
3
votes
0answers
106 views

How to resolve this equation for $f(n)$ without using $f(n-1)$

I have an equation related to some work I'm doing on Poisson distribution where I'm calculating a sequence of 100 values between a minimum and maximum value which is set by another formula. ...
2
votes
4answers
463 views

Solving Recurrence $T(n) = T(n − 3) + 1/2$;

I have to solve the following recurrence. $$\begin{gather} T(n) = T(n − 3) + 1/2\\ T(0) = T(1) = T(2) = 1. \end{gather}$$ I tried solving it using the forward iteration. $$\begin{align} T(3) ...
3
votes
1answer
66 views

An interesting partial recurrence equation

What is the closed form solution to the following partial recurrence relation? $$f(k,n) = \sum\limits_{t=0}^{m}f(k-t, n-1),$$ where $ m \geq 0$ is some fixed parameter. The boundary values are ...
1
vote
4answers
22 views

Completing simplification step when solving a recurrence

I am trying to understand a simplification step in one of the recurrence examples solved by repeated substitution in a book of algorithms problems I found on Github. I am using it for extra practice ...
1
vote
0answers
35 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
3answers
77 views

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

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 ...
0
votes
0answers
16 views

How to solve this recurrence relation and solving the power series

Take the following recurrence relation into account: $$ a_{n+2} = \frac{1}{(n+1)(n+2)} \sum_{k=0}^n (s_n - (k+1)a_{k+1})(n-k+1)a_{n-k+1} $$ I know that: $$ s_{2m+1} = \frac{(-1)^m}{(2m+1)!} $$ and ...
19
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 ...
0
votes
1answer
70 views

BMO Round 2 question [on hold]

I need help with this BMO question: The first term $x_1$ of a sequence is $2014$. Each subsequent term of the sequence is defined in terms of the previous term. The iterative formula is ...
4
votes
3answers
41 views

Stirling Numbers Proof

Prove the following: $$\sum\limits_{k=1}^{∞} (−1)^k (k − 1)! S(n,k) = 0$$ Where $S(n,k)$ is the Stirling numbers of the second kind. (Hint: Recurrence Relation) Workings: The recurrence relation ...
1
vote
3answers
17 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
0answers
24 views
+100

Let $g_n^k=p_{n+k}-p_n$, where $p_n$ is the $n$th prime. Does there exist $g_{k+1}^1=2$ such that $g_1^k,g_2^k,\ldots$ is a “Gilbreath sequence?”

Call $(S_i)_{i=1}^{\infty}$ a Gilbreath sequence if $1=\lvert S_2-S_1\rvert=\lvert \lvert S_3-S_2\rvert-\lvert S_2-S_1\rvert\rvert=\cdots$, i.e., if the sequence can be substituted for the primes in ...
2
votes
2answers
24 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) + ...
0
votes
0answers
15 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
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 ...
2
votes
2answers
39 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
1answer
29 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
316 views

Question about the “master theorem” of recurrences - no “$b$” term

I'm using the master theorem to find the asymptotic run time of recurrences. For example, for a $T(n) = 4 T(n/5) + n^1$ I find that $T(n)$ is $\Theta(n^1)$, or, simply, constant time, via the set of ...
1
vote
1answer
34 views

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$?

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$? I do not think it applies because there no $n$ term and there is no $n^k$ for a $k$ which would equal $0$.
1
vote
0answers
41 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
38 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
9 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
17 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\\ ...
2
votes
5answers
690 views

Explanation of recursive function

Given is a function $f(n)$ with: $f(0) = 0$ $f(1) = 1$ $f(n) = 3f(n-1) + 2f(n-2)$ $\forall n≥2$ I was wondering if there's also a non-recursive way to describe the same function. WolframAlpha tells ...
14
votes
0answers
333 views

Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying ...
1
vote
2answers
39 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$. ...
-5
votes
1answer
20 views

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

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
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 ...
0
votes
0answers
15 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) ...
9
votes
4answers
237 views

Help with a recurrence with even and odd terms [duplicate]

I have the following recurrence that I've been pounding on: $$ a(0)=1\\ a(1)=1\\ a(2)=2\\ a(2n)=a(n)+a(n+1)+n\ \ \ (\forall n>1)\\ a(2n+1)=a(n)+a(n-1)+1\ \ \ (\forall n\ge 1) $$ I don't have much ...
6
votes
1answer
239 views

convoluted recurrence: $f(2n)=f(n)+f(n+1)+n, f(2n+1)=f(n)+f(n-1)+1$

For the recurrence relation: $f(0)=1$ $f(1)=1$ $f(2)=2$ $f(2n)=f(n)+f(n+1)+n\ \ \ (\forall n>1)$ $f(2n+1)=f(n)+f(n-1)+1\ \ \ (\forall n\ge 1)$ (the first numbers of the sequence are: 1, 1, 2, ...
2
votes
0answers
31 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
39 views

How do I solve this recurrence? [closed]

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
49 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.
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 ...
2
votes
1answer
386 views

How to find recurrence relation of a given solution.

Determine values of the constants $A$ and $B$ such that $a_n=An+B$ is a solution of the recurrence relation $a_n=2a_{n-1}+n+5$. I know that the characteristic equation is $r-2 = 0$ which has the root ...
5
votes
4answers
4k views

What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?

This looks like a question asked earlier, but it isn't. $$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad & \text{ if } n>1 \\ 1 & \text{ if }n=1\end{cases}$$ My professor gave this to me in ...
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 ...
-2
votes
1answer
25 views
7
votes
2answers
72 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 ...
1
vote
2answers
543 views

Using recurrences to solve $3a^2=2b^2+1$

Is it possible to solve the equation $3a^2=2b^2+1$ for positive, integral $a$ and $b$ using recurrences?I am sure it is, as Arthur Engel in his Problem Solving Strategies has stated that as a method, ...