Tagged Questions
3
votes
1answer
66 views
effective way to get the integer sequence A181392 from oeis
the sequence A181392 are perfect squares and any digit in the sequence says
"I am part of an integer in which you'll find d digits "d"" (see A108571, How can we call them? "digit-valid"?)
How to get ...
1
vote
3answers
30 views
Proof that $\sum_{k=0}^m \binom{m}{k}\frac{1}{k+1} = \frac{2^{m+1}-1}{m+1}$ [duplicate]
Recently I needed to compute $E[\frac{1}{X+1}]$ where $X\sim Bin(m, \frac 1 2)$.
While expanding, I came across the sum $\sum_{k=0}^m \binom{m}{k}\frac{1}{k+1}$, which I was unable to solve. Plugging ...
1
vote
3answers
120 views
Evaluate a sum with binomial coefficients
$$\text{Find} \ \ \sum_{k=0}^{n} (-1)^k k \binom{n}{k}^2$$
I expanded the binomial coefficients within the sum and got $$\binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \dots + \binom{n}{n}^2$$
...
2
votes
1answer
42 views
Number of Distinct Resistances that can be produced from n equal resistance resisters
Here is an interesting problem:
The number of distince resistances that can be produced from n equal resistance resisters is given below.
The Sequence
Surprisingly this is also equal to the number ...
8
votes
1answer
148 views
Function mapping challange
For a given set $A=\{1, 2, 3, 4, \ldots, n\}$, find the number of non-constant
mappings (associations ) $f$ from $A$ to $A$ such that $f(k) \leq f(k + 1)$
and $f(k) = f(f(k + 1))$.
This is ...
7
votes
2answers
130 views
Summing series with factorials in
How do you sum this series?
$$\sum _{y=1}^m \frac{y}{(m-y)!(m+y)!}$$
My attempt:
$$\frac{y}{(m-y)!(m+y)!}=\frac{y}{(2m)!}{2m\choose m+y}$$
My thoughts were, sum this from zero, get a trivial ...
8
votes
5answers
348 views
Finding the smallest integer $n$ such that $1+1/2+1/3+…+1/n≥9$?
I am trying to find the smallest $n$ such that $1+1/2+1/3+....+1/n \geq 9$,
I wrote a program in C++ and found that the smallest $n$ is $4550$.
Is there any mathematical method to solve this ...
1
vote
4answers
88 views
Finding generating function for the recurrence $a_0 = 1$, $a_n = {n \choose 2} + 3a_{n - 1}$
I am trying to find generating function for the recurrence:
$a_0 = 1$,
$a_n = {n \choose 2} + 3a_{n - 1}$ for every $n \ge 1$.
It looks like this:
$a_0 = 1$
$a_1 = {1 \choose 2} + 3$
$a_2 = {2 ...
0
votes
1answer
30 views
Recurrence equation with upper and lower boundary condition
A very natural set up for recurrence equations is the following:
$$ s(0) = 0 $$
$$ s(k) = A \ s(k-1) + B $$
$$ s(M) = A \ s(M-1), $$
where $0 \le A,B \le 1$ and $0 < k < M$.
We can omit the ...
5
votes
1answer
112 views
Combinatorial puzzle
Let $\pi$ be a set of ordered pairs of natural numbers, $\pi = \lbrace (n_1,n_2) \dots (n_k ,n_{k+1})\rbrace$ (a "set of pairs").
Let $\cup \pi$ be the set $\lbrace n_1 n_2 \dots n_k ...
3
votes
1answer
45 views
An identity related to Legendre polynomials
Let $m$ be a positive integer. I believe the the following identity
$$1+\sum_{k=1}^m (-1)^k\frac{P(k,m)}{(2k)!}=(-1)^m\frac{2^{2m}(m!)^2}{(2m)!}$$
where $P(k,m)=\prod_{i=0}^{k-1} (2m-2i)(2m+2i+1)$, ...
1
vote
1answer
50 views
Triangle tiling proof
How to prove that the number of triangles in the tiling below can be found by the formula
$$\left\lfloor\frac{n(n+2)(2n+1)}8\right\rfloor\;,$$
where $n$ is the number of vertical layers? (For the ...
0
votes
0answers
20 views
Generating Function of Products [duplicate]
"A friend of mine" has generating functions $f(z)=\sum_{n=1}^{\infty} a_n z^n$ and $g(z)=\sum_{n=1}^{\infty}b_n z^n$ for the sequences $\{a_n\}$ and $\{b_n\}$. He/she would like to obtain the ...
1
vote
2answers
50 views
Lengths of increasing/decreasing subsequences of a finite sequence of real numbers
Let $x_1,\ldots,x_n$ be a finite sequence of real numbers. Let $f(\{x_i\}_{i=1}^n)=f(\{x_i\})$ be the length of the largest non-decreasing subsequence, and let $g(\{x_i\})$ be the length of the ...
2
votes
2answers
65 views
Finding the expression for $q_n$
Let $q_n$ be the number of $n$-letter words consisting of letters a, b, c and d, and which contain an odd number of letters $b$. Prove that
$$q_{n+1} = 2q_n + 4^n\qquad\forall n \geq 1 $$
and, ...
2
votes
1answer
44 views
Recurrence equation question
My question (which has been edited) relates to the following recurrence relation:
$$a_{j+2}=\frac{2 a_{j}}{j}$$
The book which I am reading says that the (approximate) solution is given by:
...
3
votes
0answers
32 views
Proving two summations equivalent [duplicate]
Let $h_n$ be an infinite sequence. I need to show that:
\begin{align}\dfrac{1}{1+x}H\left(\dfrac{x}{1+x}\right) = \sum\limits_{k=0}^\infty \sum\limits_{i=0}^k(-1)^{k-j}{k\choose i}x^kh_i
\end{align}
...
3
votes
1answer
57 views
Show that $\frac{1}{1+x}H(\frac{x}{1+x})=\sum^\infty_{k=0}[\Delta^kh_0]x^k$
For a sequence $\{h_n\}_{\geq 0}$, let $H(x)=\sum_{n\geq0}h_nx^n$. Show that:
$$\frac{1}{1+x}H(\frac{x}{1+x})=\sum^\infty_{k=0}[\Delta^kh_0]x^k$$
What I did was that by proving the $$\Delta^k ...
0
votes
2answers
49 views
Proving the formula holds for the $k$-th order differences of a sequence.
Prove that the following formula holds for the $k$-th order differences of a sequence $\{h_n\}_{n\geq0}$:
$$\Delta^kh_0=\sum^k_{j=0}(-1)^{k-j}{k \choose j}h_j$$
by using induction on $k$.
0
votes
1answer
18 views
Finding a formula for $\sum^n_{k=0}h_k$
Let the sequence $\{ h_n\}_{n\geq}$ be defined by $h_n=2n^2-n+3$. Determine the difference table, and find a formula for $$\sum^n_{k=0}h_k$$
1
vote
1answer
36 views
Sum of $nC^k$ and $k*nC^k$
How to find
$$\sum_{k=0}^n nC^k$$
and
$$\sum_{k=0}^n knC^k$$
Does this help : $\sum n=\frac{n(n+1)}{2}?$
1
vote
1answer
85 views
Sum the series : $\sum_{n\geq 1} \frac{C(n,0)+C(n,1)+C(n,2)+\cdots+C(n,n)}{P(n,n)}$
Sum the series $$\sum_{n\geq 1} \frac{C(n,0)+C(n,1)+C(n,2)+\cdots+C(n,n)}{P(n,n)}$$
The answer is given as $e^2-1$.
For getting that answer, $C(n,0)+C(n,1)+C(n,2)+\cdots+C(n,n)$ should be equal ...
17
votes
3answers
422 views
Prove an inequality on $l^2$ sequences over $F_2$
Denote $F_2$ the free non-abelian group on two letters $a, b$.
Note that any element in $F_2$ is just a word formed by letters from the set $\{a,b,a^{-1},b^{-1}\}$, and the group structure is given ...
5
votes
3answers
101 views
How to prove it? (one of the Rogers-Ramanujan identities)
Prove the following identity (one of the Rogers-Ramanujan identities) on formal power series by interpreting each side as a generating function for partitions:
...
0
votes
1answer
68 views
Binomial Distribution with dynamic probability
EDITED version to my original question...
For the coin toss problem the probability of getting exactly $k$ successes in $n$ trials is
$$
f(k;n,p) = \Pr(X = k) = {n\choose k}p^k(1-p)^{n-k}
$$
Here ...
1
vote
1answer
36 views
Generating function as Rational Function
Find the generating function for the sequence ${a_n}$ defined by:
$$a_n=4a_{n-1}-4a_{n-2}+{n\choose 2}2^n+1$$
for $n\leq 2$ and $a_0=a_1=1$. Write your answer as a rational function.
1
vote
2answers
164 views
Prove that $\sum\limits_{i=1}^n 2i\binom{2n}{n-i}= n\binom{2n}{n}$
Let n be a positive integer.
Prove that $$\sum_{i=1}^n 2i\binom{2n}{n-i}= n\binom{2n}{n}$$
5
votes
4answers
159 views
The generating function for the Fibonacci numbers
$$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$
The coefficients are Fibonacci numbers $\left\{1,1,3,5,8,13,21,...\right\}$.
Please HELP. Thanks guys.
2
votes
2answers
69 views
Evaluating $\sum_{i=0}^n(-1)^{n-i}{n \choose i}f(i)$
From Enumerative Combinatorics by Stanley:
Evaluate $$\sum_{i=0}^n(-1)^{n-i}{n \choose i}f(i)$$
where $$\sum_{n\ge 0}\frac{f(n)x^{n}}{(n)!}=\exp\bigg(x+\frac{x^2}{2}\bigg)$$
I tried splitting ...
7
votes
1answer
111 views
Approximating a sequence with funny recurrence
Consider the sequence $a_n$ defined as $a_1=a_2=1, a_{n+1}(1+a_{n})=n+1$.
This sequence describes the average number of fixed points of an involution on an $n$-set, and one can approach the problem ...
11
votes
2answers
236 views
Can the Basel problem be solved by Leibniz today?
It is well known that Leibniz derived the series
$$\begin{align}
\frac{\pi}{4}&=\sum_{i=0}^\infty \frac{(-1)^i}{2i+1},\tag{1}
\end{align}$$
but apparently he did not prove that
$$\begin{align}
...
0
votes
1answer
56 views
Generating functions for sum of powers of two
I have the recurrence:
$a_1 = 2$
$a_{n+1} = 2^n + a_n$
How can I use generating functions to compute a closed form for $a_n$?
Here is what I did on my own:
Let $A(x) = \sum_{n \geq 1} ...
0
votes
0answers
47 views
Iterate over combinations ordered by sum
I have a sorted list of a large number of primes. I want to iterate over combinations of fixed size $n$ in increasing order of their sum. Naturally the standard approach for $n=4$:
$$s_0 = \sum(A, ...
2
votes
0answers
130 views
Find a tight upper bound of the following expectation.
I am stuck in finding a tight upper bound (as tight as possible) of the following expectation $$E\left [ (1-a\cdot b^{X})^{m} \right ]$$ where $X\sim B(n-1,p)$ is a binomial random variable.In ...
10
votes
2answers
140 views
Integer sequences which quickly become unimaginably large, then shrink down to “normal” size again?
There are a number of integer sequences which are known to have a few "ordinary" size values, and then to suddenly grow at unbelievably fast rates. The TREE sequence is one of these sequences, which ...
1
vote
2answers
56 views
Error propagation through recurrence relation
I want to see how the error propagates on a mapping that I have. I have proven that $$|f(x+\varepsilon)-f(x)|=\varepsilon(1+\varepsilon),$$
let $\varepsilon_n$ be the error after $n$ applications of ...
2
votes
2answers
90 views
Finding Binomial expansion of a radical
I am having trouble finding the correct binomial expansion for $\dfrac{1}{\sqrt{1-4x}}$:
Simplifying the radical I get: $(1-4x)^{-\frac{1}{2}}$
Now I want to find ${n\choose k} = ...
0
votes
0answers
10 views
Qualifying Parameters
you have two parameters, 1) rates of trees per land size, ranging from 30%-100%, and 2) rates of birds per land size, ranging from 5%-30%
goal is that you're trying to find out which is overall ...
2
votes
0answers
266 views
Prove that sum is finite with the help of generating function
Please help me to prove that the following sum is finite
$$
\sum_{j=2l-2}^{\infty}j!\, a_j^{(l)},
$$
here the generating function of $\displaystyle{a_j^{(l)}}$ is ...
36
votes
7answers
783 views
Problems regarding $\{x_n \}$ defined by $x_1=1$; $x_n$ is the smallest distinct natural number such that $x_1+…+x_n$ is divisible by $n$.
Let me denote a sequence of distinct natural numbers by $x_n$ whose terms are determined as follows:
$x_1$ is $1$ and $x_2$ is the smallest distinct natural number $n$ such that $x_1+x_2$ is divisible ...
0
votes
1answer
140 views
Sum of following binomial series :
I need to solve this binomial summation but cant seem to get it using binomial identities I learnt in school and college first-year:
$$S=\sum_{i=q}^{p-q}{\binom{i}{q}}{\binom{n-i}{p-q}}$$
p,q,n are ...
3
votes
1answer
291 views
How many length n binary numbers have no consecutive zeroes ?Why we get a Fibonacci pattern? [duplicate]
Possible Duplicate:
How many $N$ digits binary numbers can be formed where $0$ is not repeated
I am really embarrassed to ask this as it seems like a textbook question.But it is not, and I ...
1
vote
1answer
47 views
Finding an element of the intersection of an infinite sequence of “compatible” sets of infinite sequences
Let $A$ be a set. Let $A^\omega$ denote the set of infinite sequences of members of $A$ (i.e., functions from $\omega$ to $A$). Define $\omega_n = \omega \setminus \{n\}$. Let $A^\omega_n$ denote the ...
9
votes
2answers
387 views
Does this double series converge?
$$\sum\limits_{y=1}^{Y}\sum\limits_{z=1}^{y} a^{y-1} b^y \binom{y-1}{z-1} (c + 2z)^d $$
Does this series converge when $Y=∞$? If the series converges, what does it converge to? If the series does not ...
4
votes
3answers
172 views
What is the next number of this sequence?
Consider the sequence $ (a_{n})_{n \in \mathbb{N}} $ of positive integers whose first few entries are
$ 2 ~~ 6 ~~ 20 ~~ 70 ~~ 252 ~~ \ldots $
Now, consider the infinite matrix
...
0
votes
0answers
46 views
Golomb Sequence Approximation Proof
I came across the Golomb Sequence in a book (Programming Challenges), where we are asked to determine $a_n$ given $n$, in a 'clever' fashion. It is a non-decreasing sequence with number $n$ appearing ...
5
votes
3answers
106 views
Use of Recursively Defined Functions
Recursion is definitely fascinating and can generate sequences that would need lengthy functions.
While doing combinatorics, I found that certain counting problems and some probability computation ...
6
votes
3answers
137 views
How to transform this infinite sum
How to transform this infinite sum
$$\sum_{i\geq0}\frac{x^i}{(1-x)(1-x^2)\cdots(1-x^i)}$$
to an infinite product
$$\prod_{i\geq1}\frac{1}{1-x^i}$$
0
votes
2answers
115 views
Different recurrence relations that model the same problem
I'm trying to solve the following counting problem, but my answer is different from the textbook's:
Find a recurrence relation for the number of n-digit ternary sequences that have the pattern "012" ...
4
votes
4answers
162 views
Closed form for $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$
How can I calculate the following sum involving binomial terms:
$$\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$$
Where the value of n can get very big (thus calculating the binomial ...
