# Tagged Questions

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 ...
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 ...
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$$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$, ...
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 ...
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 ...
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 ...
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, ...
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: ...
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} ...
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 ...
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$.
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$$
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}?$
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 ...
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 ...
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: ...
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 ...
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.
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}$$
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.
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 ...
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 ...
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} ...
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} ...
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, ...
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 ...
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 ...
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 ...
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} = ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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}$$
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" ...
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 ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 117, "mathjax_display_tex": 32, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9179267287254333, "perplexity_flag": "head"}