2
votes
1answer
18 views

Clarification regarding the Josephus problem in Concrete Mathematics (Knuth, et al)

In page 9 of Concrete Mathematics, regarding the Josephus Problem, they state that "each person's number has been doubled then decreased by 1". $J(2n) = 2J(n) - 1$, for $n \ge 1$ I don't quite ...
1
vote
1answer
37 views

Evaluation of a Hankel-like determinant

I consider the following determinant (Hankel-like?) $$ [f_1,f_2,...,f_n]:=\begin{vmatrix} f_1 & f_2 & \cdots & f_{n-1} & f_n\\ n-1 & f_1 & \cdots & f_{n-2}& f_{n-1}\\ 0 ...
3
votes
1answer
37 views

What's the time complexity of T(n)=nlogn+T(n-1)?

The title says it all. The best I can come up with is that this expands to T(0) + 1log 1 + 2log 2 + ... + (n-1)log (n - 1) + nlog n which is ...
1
vote
2answers
39 views

Recurrence with multiplication

Let $\{a_{n}\}$ be a sequence of nonnegative numbers such that $a_{n} = 2^{n}a_{n - 1}^{3/2}$. If $a_{1}$ is sufficiently small, why must $a_{n} \rightarrow 0$ as $n \rightarrow \infty$?
1
vote
2answers
41 views

Find a recurrence for in , the number of integer compositions of n which only have 1s and 2s as parts.

Find a recurrence for $$i_n$$ the number of integer compositions of $n$ which only have $1$s and $2$s as parts. How do you approach this problem?
1
vote
2answers
65 views

How to solve this mathematically

This is a question given in my computer science class. We are given a global variable $5$. Then we are to use keyboard event handlers to do the following: On event keydown double the variable and on ...
0
votes
1answer
72 views

Solving this recursive function $f(x)=f(x-k)+f(x/k)$.

How to solve or simplify the following recursive function? $f(x)$ is defined only for whole numbers as follows: $$f(x)=\begin{cases} 1 & \mbox{if } x<k; \\ f(x-k)+f(x/k) ...
0
votes
1answer
42 views

recurrence relation question.

I have this expression: $I_{n} = \int_0^1 \frac{x^{n-1}}{2-x} dx$ for $n=1,2,3,\ldots$ I have been asked to show that by writing $x^n = x^{n-1} (2-(2-x))$ that the recurrence relation $I_{n+1} = 2I_n ...
-1
votes
1answer
57 views

I am not how they got characteristic equation from the given equation.

![can someone tell me they got characteristic equation from the given recursive equation.][1] i know how to do the rest of problem but getting characteristic equation stopped me. The recurrence is ...
2
votes
3answers
75 views

Solving Recurring Relations

Can you please help, my son has been trying for over two hours now to solve the following: A sequence of terms $\left\{u_n\right\}$ is defined for $n\geq 1$, by the recurrence relation: ...
2
votes
1answer
65 views

An inequality property of the Fibonacci sequence

Given the Fibonacci sequence $F_n$, Wikipedia says (http://en.wikipedia.org/wiki/Fibonacci_number#List_of_Fibonacci_numbers) $$ F_{2n-1} = F_n^2+F^2 _{n-1}$$ so that $$F_{2n-1}>F^2_n$$ What is the ...
1
vote
1answer
37 views

Simplifying a Recurrence Relation

$(n_i) $ is a sequence of integers satisfying $n_{i+1}=a_{i+1}n_i+n_{i-2}$. Consider a subsequence $(n_{i_j}).$ Can $n_{j_{i+1}}$ be written in terms of $n_{j_i}$? An attempt is to use the recurrence ...
0
votes
3answers
79 views

Recurrence relation of two next terms

For the recurrence relation, $a_{n+2}=3a_{n+1}-2a_n$ with $a_0=2$ and $a_1=3$, compute the first six terms of the sequence and derive a closed form formula for this sequence. So I'm totally lost with ...
1
vote
1answer
122 views

Alternative solutions to $n^2+n = k^2+k + 2kn$

Consider this equation: $n^2+n = k^2+k + 2kn$ I want to find the set of non-negative integer n,k that satisfies the equation. I tried to write $n$ as $k$ by solving the equation with $n$ as root ...
1
vote
1answer
208 views

Establishing formula from recurrence

Can anyone tell me how do we establish a formula from a given recurrence relation? Take the example of $f(n) = 2f(n-1) + 1$, $n \in \mathbb{Z^+}$, $f(1) = 1$ When I write out the first few values, it ...
20
votes
4answers
505 views

Evaluating $\sqrt{1 + \sqrt{2 + \sqrt{4 + \sqrt{8 + \ldots}}}}$

Inspired by Ramanujan's problem and solution of $\sqrt{1 + 2\sqrt{1 + 3\sqrt{1 + \ldots}}}$, I decided to attempt evaluating the infinite radical $$ \sqrt{1 + \sqrt{2 + \sqrt{4 + \sqrt{8 + \ldots}}}} ...
0
votes
1answer
157 views

Convert a recurrence relationship into an algebraic equation

I have a piece of code that describes a recursive relationship to produce a logarithmic sweep: ...
1
vote
0answers
99 views

How to find the recurrence polynomial?

Problem: If $f$ is a polynomial with unknown roots $x_1,-x_1,x_2,-x_2\ldots,x_b,-x_b \quad (b \in \mathbb{N})$ and can be expressed as (known expansion): $$f(x)=\sum_{a=0}^{2b}f_ax^a\quad(b \in ...
0
votes
0answers
484 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, ...
3
votes
1answer
254 views

Non-linear recurrence problem

How to convert $p_n$ to an expression in terms of $n$ if $3p_{n-1}^2 - p_{n-2}=p_{n}$ and $p_0=5, p_1=7$? This is a problem I haven't been able to finish for two days, please help. This question ...
1
vote
1answer
146 views

Question about generating function in an article

Could someone explain what $R(x)$ and constant $c_1,c_2,...,c_k$ are in this article about characteristic polynomial in proof 3? If that someone could rephrase it, because it seems not so clear in ...
0
votes
1answer
86 views

Can we express $p_n$ in terms of $p_0, p_1$ and $n$?

$p_0=a$, $p_1=b$, $bp_n=p_{n+1}+p_{n-1}$ express $p_n$ in terms of $a,b,n$. Any help would be appreciated, because you guys are splendid.
0
votes
1answer
800 views

Rearranging a general closed form linear recurrence sequence

I have the following general closed form linear recurrence equation: $$x_n=r^{n-1}a+\left(\frac{r^{n-1}-1}{r-1}\right)d, \qquad (n=1,2,3,...)$$ and the next stage in the text shows the equation ...
0
votes
1answer
563 views

recurrence relation on bank interest

Invest 1000 dollars at bank at 3 percent interest compound annually. Every year the bank deducts 15 dollars in charges. If $A_n$ is the value of the investment at the end of $n$ years write down a ...
2
votes
1answer
327 views

Proof of closed form Hofstadter G-Sequence

I'm working through a discrete maths text book and was stumped as to how to prove the closed form solution of the Hofstadter G-Sequence $a(0) = 0$ and $a(n) = n - a(a(n-1)), n \geq 1$ The closed ...