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

learn more… | top users | synonyms

1
vote
2answers
364 views

solving inhomogeneous recurrence relation

I had encountered an inhomgeneous equation of the type : $$f(n)=h(f(n))+g(n)$$ below is the equation. $$f(n)=\begin{cases} f(n-1)+2^{(n-1)/2},&\text{if }n\text{ is odd}\\\\ ...
9
votes
1answer
296 views

Recurrence equation similar to a geometric progression

I have the following recurrence relation: $$T(i) = \sqrt{T(i-1) \left(T(i+1) + k\right)},$$ with $k \geq 0$, a fixed constant. I know that when $k=0$, we have: $$T(i) = \sqrt{T(i-1) T(i+1)},$$ which ...
2
votes
3answers
94 views

Corresponding numerator of the fraction

I am stuck at this question cant think of how to resolve this, sorry I did try to do working but can't think of any right solution. The question is If the denominator is $9900$, then what is the ...
3
votes
1answer
824 views

In how many different ways can we fully parenthesize the matrix product?

We have a finite number of matrices that we wish to compute the product of . Say we wish to compute a product of n matrices and we have the subroutine to compute a ...
0
votes
0answers
41 views

Estimating the recurrence $T(n,i) = (\lfloor\frac{n-i}{i}\rfloor \cdot i ) + T(i + (n \operatorname{rem} i), (n \operatorname{rem} i))$

Given $i < n/2$ and denoting $[x]$ to be an integer part of $x$ (floor$(x)$) and $(a \operatorname{rem} b)$ to be a reminder when $a$ is divided by $b$. $$ T(n,i) = ...
2
votes
6answers
275 views

I know that, $S_{2n}+4S_{n}=n(2n+1)^2$. Is there a way to find $S_{2n}$ or $S_{n}$ by some mathematical process with just this one expression?

$S_{2n}+4S_{n}=n(2n+1)^2$, where $S_{2n}$ is the Sum of the squares of the first $2n$ natural numbers, $S_{n}$ is the Sum of the squares of the first $n$ natural numbers. when, $n=2$ ...
1
vote
1answer
81 views

Complexity of recurrence equation

what is the complexity of this equation ? $T(n) = 2*T(\sqrt n) + \log n$ and T(2) = 1.
2
votes
1answer
372 views

How to complete this proof regarding closed form of tower of hanoi problem? [duplicate]

Possible Duplicate: can one derive the $n^{th}$ term for the series, $u_{n+1}=2u_{n}+1$,$u_{0}=0$, $n$ is a non-negative integer I'm trying to learn induction through practise and I'm ...
2
votes
1answer
63 views

Flawed twofold induction on an inequation (but where?)

The following induction is flawed because the result admits a counter-example, but I can't find where is the flaw. Please advise. [Edit: As pointed out in the answer, the error was in the base case. ...
3
votes
2answers
181 views

A partial recurrence equation

What is the closed form solution to the following partial recurrence relation? $$ q(n,m) = \frac{q(n-1,m-1)}{n} - q(n-1,m) $$ where $q(0,m)=0$ for all $m > 0$ and $q(n,0) = (-1)^n$ for all $n \geq ...
4
votes
4answers
156 views

Expansion of $x^4\over1+x^2$ into a power series

I calculated the generating function $A(x)$ of the recurrence $a_n = a_{n-2} - 2a_{n-3}$, $(n \ge 0, a_0 = a_1 = 0, a_2 = 2)$ and I have no clue on how to expand it into a power series in order to ...
3
votes
1answer
682 views

Need refresher on z-transforms and difference equations

I recently tried showing someone else how to solve a difference equation using z-transforms, but it's been a long time and what I was getting didn't look right. I was trying to solve the recurrence ...
7
votes
1answer
126 views

Put a mouse to the last cell

We have (n=12) cells $C_1, C_2 ,\dots, C_{12}$ which are initially empty. At each step, we can do one of two operations: $\mathbf{P}$: Put only in the first cell $C_1$ 2 mice. $\mathbf{M}$: Move ...
2
votes
4answers
339 views

can one derive the $n^{th}$ term for the series, $u_{n+1}=2u_{n}+1$,$u_{0}=0$, $n$ is a non-negative integer

derive the $n^{th}$ term for the series $0,1,3,7,15,31,63,127,255,\ldots$ observation gives, $t_{n}=2^n-1$, where $n$ is a non-negative integer $t_{0}=0$
0
votes
2answers
969 views

Master theorem solving

I'm starting to study the master theorem, why does something like $$T(n) = aT(n/b)+f(n)$$ solves to $$f(n)^{\log_ba}$$ ? I'm a bit confused on the resolution
1
vote
4answers
375 views

Solving a recurrence of polynomials

I am wondering how to solve a recurrence of this type $$p_1(x) = x$$ $$p_2(x) = 1-x^2$$ and $$p_{n+2}(x) = -xp_{n+1}(x)+p_{n}(x).$$ I am wondering, how could one solve such a recurrence. One way ...
13
votes
1answer
195 views

Integer Sequence “sums of digits of squares”.

For all $n \in \mathbb{N}$ we define the function $\delta(n)=p$, where $p$ is sums of digits of $n^2$. For example if $n=17, \ n^2=289$, then $\delta(17)=2+8+9=19$. Let $a_k$ is a monotonically ...
1
vote
1answer
72 views

Can one solve a recurrence that contains a function?

I'd like to solve a recurrence, so I've been reading about solving recurrences, and all the ones I've seen solved involve only previous terms of the recurrence, and constants. My recurrence is $$t(n) ...
0
votes
0answers
332 views

What are the mathematical and “real world” applications of “quadratic maps”, a type of dynamical system?

If we suppose that we can get a generating function for any "quadratic map (as in dynamical systems)", what are the mathematical applications? Also, what are the "real world" applications of this? ...
1
vote
3answers
368 views

Recurrence substitution method

I just want to see if I did this right. I need to show that $T(n) = 3T(n/4) + n\log n$ shows that $T(n) = O(n\log n)$ using substitution method in recurrence. $$T(n) = 3c(n/4 \log n/4) + n\log n$$ ...
4
votes
2answers
195 views

Enumerate certain special configurations - combinatorics.

Consider the vertices of a regular n-gon, numbered 1 through n. (Only the vertices, not the sides). A "configuration" means some of these vertices are joined by edges. A "good" configuration is one ...
2
votes
1answer
227 views

Finding Probability Generating function for $P\left\{ X > n+1\right\} $

I am trying to find probability generating function for $P\left\{ X > n+1\right\} $. Let X be a random variable assuming the values $0, 1, 2, ...$. The notation both for the distribution of $X$ ...
22
votes
2answers
525 views

Is $\sin\left(\frac{\pi}{2}\sin\left(\frac{\pi}{2}\cdots\sin x\cdots\right)\right)=\frac4{\pi}\sum\limits_{k=0}^\infty\frac{\sin(2k+1)x}{2k+1}$?

We can see intuitively that $$ f(x)=\sin\left(\frac{\pi}{2}\sin\left(\frac{\pi}{2}\sin\left(\frac{\pi}{2}\cdots\sin{x}\cdots\right)\right)\right) $$ is the square wave with period $2\pi$ and has the ...
4
votes
2answers
300 views

Understanding why the roots of homogeneous difference equation must be eigenvalues

There is some obvious relationship between the root solutions to a homogeneous difference equation (as a recurrence relation) and eigenvalues which I'm trying to see. I have read over the wiki article ...
2
votes
3answers
116 views

recurrence solution to gambler's ruin

From DeGroot 2.4.2, let $a_i$ be the conditional probability that the gambler wins all $k$ given gambler is at $i$. $a_i = pa_{i+1} + (1 - p)a_{i-1} $ It's not clear from the text what steps are ...
8
votes
4answers
473 views

Closed form for a non-linear recurrence

Does equation $a_n=\sqrt{a_{n-1}+6}$ with $a_1=6$ have a closed form? I've found no linearization method. Any suggestion or hint will be highly appreciated.
1
vote
1answer
84 views

What would be possible if we could perform repeated “linear mapping” on recurrences?

We can label the terms in a sequence as $a_n$ for the $n$th term. Then the generating function for the sequence can be defined as $$ A(x) = \sum_{n=0}^\infty{a_n x^n} $$ If we have a closed form for ...
0
votes
1answer
124 views

Find $y=\sum_{k=0}^{\infty}b_k z^{\frac{2k+1}{3}}$ if $y=\sum_{k=0}^{\infty}a_k x^{2k+1}$ and $z=\sum_{k=1}^{\infty}k a_k x^{2k+1}$

Suppose that the sequence $\{a_i\}_{i=0}^\infty$ is known and that, $$ y=\sum_{k=0}^{\infty}a_k x^{2k+1},\quad\text{and}\quad z=\sum_{k=1}^{\infty}k a_k x^{2k+1} $$ are two convergent power series for ...
0
votes
1answer
100 views

Demonstration of a recurence formula

I would like to demonstrate a recursive formula that I have inferred. My background in mathematics is not quite as high as I hoped and although I have tried to apply the basic tricks that go with the ...
14
votes
4answers
344 views

A recurrence relation for the Harmonic numbers of the form $H_n = \sum\limits_{k=1}^{n-1}f(k,n)H_k$

Working on Harmonic numbers, I found this very interesting recurrence relation : $$ H_n = \frac{n+1}{n-1} \sum_{k=1}^{n-1}\left(\frac{2}{k+1}-\frac{1}{1+n-k}\right)H_k ,\quad \forall\ ...
1
vote
2answers
246 views

Fibonacci Sequence Variants

I learnt about finding the $n$th Fibonacci number using matrix exponentiation in $\log n$ time. Then I tried finding similar formula for sequences of the form $$S_{n} = S_{n-1} + S_{n-2} + a n + b$$ ...
3
votes
1answer
135 views

A difference equation related to RW on Hypercube

I am trying to solve the following recurrent relation $$ T(n)=\frac{n}{m}T(n-1)+\frac{m-n}{m}T(n+1)+1, \,\, \text{subject to } T(m)=0 $$ Where $0\leq n\leq m$ and $m$ is a fixed integer. I have ...
1
vote
2answers
37 views

What is $f(t)=X_{t+1}$, if $X_{t+1}=(1-p)(1-X_{t})+pX_{t}$ and $X_{0},p \in [0,1]$?

What is $f(t)=X_{t+1}$, if $X_{t+1}=(1-p)(1-X_{t})+pX_{t}$ and $X_{0},p \in [0,1]$? And what are general methods for finding functions defined by such recurrent equations?
1
vote
1answer
642 views

Ulam's problem - guessing a chosen number in a set

I tried to solve the following problem, which I found in the book "Discrete Mathematics and Its Applications", by Kenneth Rosen (Problem 28 of the section 7.3 of the 6th Edition): Suppose someone ...
3
votes
0answers
66 views

Recurrence relation induction [duplicate]

Possible Duplicate: Solving the recurrence $t(n)=(t(n-1))^2 + 1$ Show that the number of binary trees of height less than or equal to $n$ is given by the recurrence \begin{align*} ...
2
votes
5answers
280 views

Solving the recurrence $t(n)=(t(n-1))^2 + 1$

I am trying to solve the following recurrence relation: \begin{align*} t(1) & = 1, \\ t(n) & =(t(n-1))^2 + 1. \end{align*} I need to prove that $t(n)= k^{2^{n}}$ for some constant $k$. What is ...
5
votes
1answer
168 views

Solving Recurrence $T_n = T_{n-1}*T_{n-2} + T_{n-3}$

I have a series of numbers called the Foo numbers, where $F_0 = 1, F_1=1, F_2 = 1 $ then the general equation looks like the following: $$ F_n = F_{n-1}(F_{n-2}) + F_{n-3} $$ So far I have got the ...
3
votes
1answer
157 views

$\mu$-recursive definition of ulam (3n+1) function

$\newcommand{\ulam}{\operatorname{ulam}}$ The ulam function is defined as $$ \ulam(x) = \begin{cases} 1 & x = 1 \\ \ulam\left( \frac{x}{2}\right) & x \text{ even}\\ \ulam(3x+1) & ...
6
votes
1answer
3k views

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

While self-studying Discrete Mathematics, I found the following question in the book "Discrete Mathematics and Its Applications" from Rosen: Suppose the function $f$ satisfies the recurrence ...
3
votes
2answers
104 views

Solving a recurrence of a sequence

The sequence $a_n$ is given by recurrence $$a_0=0,a_1=1,a_n=a_{n-2}+n+4, n>2$$ How to find the general term I am interested on different approach. Can generating functions help
11
votes
1answer
920 views

Solving a Nonlinear Recursion

In the course of some research computations I have been doing, I run up against a recursion $$ a_{n+3} = a_{n+2}a_{n+1} - a_n $$ I've tried to find out if it's possible to solve recursions of this ...
0
votes
1answer
231 views

Fibonacci sequence, strings without 00, and binomial coefficient sums

Refer to the sequence $S$ where $S_n$ denotes the number of n-bit strings that do not contain the pattern 00. By considering the number of n-bit strings with exactly i 0's, show that $\displaystyle ...
1
vote
4answers
154 views

Reccurence relation: Lucas sequence

I need to solve the given recurrence relation:$$L_n = L_{n-1} + L_{n-2},$$ $n\geq3$ and $ L_1 = 1, L_2 =3$ I'm confused as to what $n\geq3$ is doing there, since $L_1$ and $L_2$ are given I got ...
2
votes
0answers
76 views

Two terms approximation of a recurrence [closed]

Find an approximation up to the second term of $z_n$ where $z_{n+2}=z_{n+1}+\sqrt{n}z_{n}$ and $z_{2}=2z_{1}>0$.
5
votes
3answers
132 views

Prove that this recurrence always cycles

If $n$ is a nonnegative integer, let $S_n=\{0, 1, 2, \dots, 2n+1\}$. For $t\in S_n$ repeatedly perform if t is even t = t/2 else t = (n + 1 + ⌊t/2⌋) ...
0
votes
1answer
119 views

Solving heterogeneous successions

I know how to get the explicit formula for homogeneous successions, kinda. What I do is get the characteristic equation, get the solutions and then solve a system to obtain the values of A,B,C... ...
4
votes
4answers
210 views

Recurrence relation $C_n = n + 1 + \dfrac{2}{n}\sum\limits_{k=0}^{n-1}C_k$.

A Discrete Mathematics book from which I'm self-studying ("Discrete Mathematics and Its Applications", by Kenneth Rosen) asks me to do the following: Given the following recurrence relation: $$C_n = ...
4
votes
4answers
1k views

Closed form solution of Fibonacci-like sequence

Could someone please tell me the closed form solution of the equation below. $$F(n) = 2F(n-1) + 2F(n-2)$$ $$F(1) = 1$$ $$F(2) = 3$$ Is there any way it can be easily deduced if the closed form ...
2
votes
2answers
73 views

What's $T\left(n\right)$?

If $T\left( n \right) = 8T\left( n-1 \right) - 15T\left( n-2 \right); T\left(1\right) = 1; T\left( 2 \right) = 4$, What's $T\left(n\right)$ ? I use this method: Let $c(T(n) - aT(n-1)) = T(n-1) - ...
0
votes
4answers
87 views

How to confirm if my explicit formula is right?

I have to determine an explicit formula for $$a_n=5a_{n-1}+6a_{n-2}$$ Initial values are $$a_0=2\\a_1=-1\\n>=2$$ My answer is $$a_n = \frac{1}{7}\cdot 6^n+\frac{13}{7}\cdot (-1)^n$$ Which I ...