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

learn more… | top users | synonyms (2)

0
votes
1answer
25 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 ...
13
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
1
vote
1answer
29 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
20 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
26 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
49 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
70 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
98 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
21 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
35 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
19 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 ...
-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
37 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
104 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
79 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
62 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
43 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
106 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
46 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
261 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} = ...
1
vote
3answers
53 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 ...
1
vote
1answer
50 views

How to write $\frac{27-17x}{2x^2-x+1}$ as a series to solve this recurrence relations problem?

The relation is: $$a_n=a_{n-1}-2a_{n-2}+4^{n-2}$$ $$a_0=2, a_1=1$$ I managed to reduce the problem to the generating function: $$A(x)=\frac{2-9x+5x^2}{(1-4x)(1-x+2x^2)}$$ and then I got this: ...
3
votes
0answers
100 views

How can I convert a recursive equation to a non-recursion one? [duplicate]

While I am aware of several other similar question which have been asked in the past, my mathematical education only extends through calculus, making them beyond my comprehension, and I believe this ...
1
vote
2answers
24 views

Recurrence. Number of sequences.

Let $q_n$ be amount of sequences, where length of sequence is $n$. The sequences are constructed from elements $\in \{a,b,c,d\}$ . In sequecne 'b' occurs odd times. For example: $$n = 10$$ ...
1
vote
1answer
36 views

How to solve this multivariable recursion?

How to solve this multivariate recursion?: $$a(m, n, k) = 2a(m-1, n-1, k-1) + a(m-1, n-1, k) + a(m-1, n, k-1) + a(m, n-1, k-1)$$ where $m, n, k$ are positive integers. Edit: $a(0,0,0) = a(1,0,0) = ...
1
vote
1answer
64 views

Using induction for sequences defined by recursion, such as $a_{n+1} = \frac14(a_n^2 +3)$

Let the sequence $\{a_n\}$ be defined by $a_{n+1} = \frac14(a_n^2 +3)$. We want to prove that if the first term $a_1$ is between $0$ and $1$ then the sequence converges. My question is why do we ...
3
votes
1answer
38 views

“Multiplication” of two linear recurrence relations

Array $a_n$ is defined as: $$a_0 = 1, \quad a_{n+1} = k_{a1}a_{n} + k_{a0}$$ Array $b_n$ is defined as: $$b_0 = 1, \quad b_{n+1} = k_{b1}b_{n} + k_{b0}$$ Array $c_n$ is defined as: $$c_n = ...
1
vote
2answers
40 views

Solution for recurrence $T(n+1) = T(n) + \lfloor \sqrt{n+1}\rfloor $ [duplicate]

ould someone please give me an idea as to how the solve the following. $$T(1) = 1$$ $$T(n+1) = T(n) + \lfloor\sqrt{n+1}\rfloor$$ I converted the recurrence to $T(n) = T(n-1) + ...
1
vote
1answer
44 views

Multiples of 11 in a Fibonacci-like sequence formed by concatenation instead of addition

Let $A_1=0$ and $A_2=1$ and suppose that the number $A_n$ is obtained from the decimal expansions of $A_{n-1}$ and $A_{n-2}$. For example $A_3=A_2A_1=10$; $A_4=A_3A_2=101$; $A_5=A_4A_3=10110$. ...
0
votes
0answers
22 views

Is there a general solution to this phase-shifted system of equations?

This is a (more general) question related to "Estimated solution to system of equations with phase-shifted functions". Given this system of two equations and two unknown functions: $$ y_1(t) = ...