# Tagged Questions

For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the *base case*, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant ...

73 views

### Prove the number comparisons it takes to find the min and max of a list by the split and conquer method

Prove that the number of comparisons it takes to find the min AND max of a list by the split and conquer method (split a list in half until there are multiple subsets of just 2 elements and compare ...
73 views

### Prove: $1+{n\choose 1}\cos\phi+{n\choose 2}\cos2\phi+…+{n\choose n}\cos n\phi=2^n\cos^n\frac{\phi}{2}\cos\frac{n\phi}{2}$

Prove: $\displaystyle 1+{n\choose 1}\cos\phi+{n\choose 2}\cos2\phi+...+{n\choose n}\cos n\phi=2^n\cos^n\frac{\phi}{2}\cos\frac{n\phi}{2}$ I used induction: For $n=1$ equality holds. For $n=k\colon$...
95 views

54 views

### Finding a closed form for the recursively defined function using the substitution method.

This is a question from a problem set I had to do for one one of my courses. The following recursively defined function is given \begin{equation*} T(n) = \begin{cases} 1, & if \ n=0 \\ 4, & ...
39 views

### Show that $n^{n-3} \ge n!$ for n=9, 10,…

Show that $n^{n-3} \ge n!$ for n=9, 10,... I have tried to n=9 $9^{9-3} = 9^6 = 531411$ $9! = 362880$ So $9^6 \ge 9!$ is true My question is how do I prove it by every for n=9, 10,... by ...
179 views

68 views

### Upper estimate for partial sums of the series $\sum 1/n^3$

I'm looking for a proof of: $$1 + {1\over 8} + {1 \over 27} + \dots + {1 \over n^3} < 1.5 − {1 \over n}$$ for all integers $n>2$. I have been working on proof by mathematical induction for a ...
48 views

54 views

48 views

### how to solve this induction problem?

An m × n array A of real numbers is a Monge array if for all i, j , k and l such that 1 ≤ i < k ≤ m and 1 ≤ j < l ≤ n, we have A[i,j] + A[k,l] ≤ A[i,l] + A[k,j] In other words, whenever we pick ...
52 views

### Summation proof- struggling to see a way to prove

I have found that the summation attached gives a general value of 1/(n+1) for the first few values of n=0,1,2,3.... I would like to prove that this is true for all n and I assumed that the best way ...
### Prove by induction: $\sum\limits_{k=1}^{n}\frac{1}{2^k}\tan\frac{x}{2^k}=\frac{1}{2^n}\cot\frac{x}{2^n}-\cot x,x\neq k\pi,k\in \mathbb{Z}$
$\sum\limits_{k=1}^{n}\frac{1}{2^k}\tan\frac{x}{2^k}=\frac{1}{2^n}\cot\frac{x}{2^n}-\cot x,x\neq k\pi,k\in \mathbb{Z}$ Base Case: For $n=1$, \$\frac{1}{2}\tan\frac{x}{2}=\frac{1}{2}\cot\frac{x}{2}-\...