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 ...

28 views

$n$ points on a circle connect by lines, the sum of the internal angles is $(n - 1) 180$°

I am trying to understand a proof by induction on a geometry problem: For all $n\geq 3$, if $n$ distinct points on a circle are connected in consecutive order by straight lines, then the ...
73 views

Using induction for sequences defined by recursion, such as $a_{n+1} = \frac14(a_n^2 +3)$

Let the sequence $\{a_n\}$ be defined by $a_{n+1} = \frac14(a_n^2 +3)$. We want to prove that if the first term $a_1$ is between $0$ and $1$ then the sequence converges. My question is why do we ...
110 views

51 views

Simplexes in $\mathbb R^n$ have at most $n+1$ points

This is an exercise from the book Espaços Métricos (metric spaces) by Elon Lima. I'm translating it (the part of it that I'm having trouble with): Show that if $X\subset\mathbb R^n$ is such that ...
258 views

strong induction example

There is following example given in a book. I am not sure how do we conclude that $a$ is divisible by prime? See this section: Case 2 ($k + 1$ is not prime): In this case $k+1=ab$ where $a$ and ...
115 views

${n \choose k}\leq n^k$

Let $n$ et $k\in \mathbb{N}$ such that : $k\leq n$ Show that :$${n \choose k}\leq n^{k}$$ My thoughts: note that for all $\ k\leq n$ : $${n \choose k}=\frac{n!}{k!(n-k)!}$$ To prove ...
32 views

88 views

Simplify sum of factorials with mathematical induction

I want to prove with mathematical induction that: $$\sum_{i=1}^n i \cdot i! = (n+1)! - 1$$ So in the first step we define $n = 1$: $$\sum_{i=1}^1 i \cdot i! = 1 \cdot 1! = 1 = 2! - 1$$ In the ...
57 views

Prove that if a set A of natural numbers contains $n_0$ and whenever A contains k it also contains k+1.

Prove that if a set A of natural numbers contains $n_0$ and that whenever A contains k it also contains k+1. Prove that A contains all natural numbers $\geq n_0$ This is rather similar to a ...
115 views

Prove Bernoulli inequality if $h>-1$

Qi) Prove Bernoulli's inequality If $h> -1$, then $(1+h)^n \geq 1+nh$ Qii) why is this Trivial is $h>0$ Something i have always been lucky with is having a lot of intuition to go on with ...
30 views

230 views

Inequality of the Fibonacci sequence and the golden ratio

How can I prove that for each $n\in\Bbb Z^+$ $$\frac{f_{2n}}{f_{2n-1}}\leq\frac{1+\sqrt{5}}{2}$$ where each $f_i$ is a term of the Fibonacci sequence. Any help is really appreciated
74 views

62 views

How to prove this equation by induction?

I am trying to prove this equation by mathematical induction $$f_{n+1}f_{n-1} = f_{n}^{2}+(-1)^n$$ is true where $f_{n} =$ the nth number in the Fibonacci sequence. I don't quite get how to do this ...
82 views

Want to ensure my proof is rigourous enough.

Question. Prove: $0 \leq x < y$ then $x^n < y^n$ $\forall n \in \mathbb{N}$ I'm particularly bad at proving obvious things but here it goes. ( please be super strict on analyzing my proof ...
91 views

Induction and basic assumptions in Graph Theory

I am beginning to work through a text in graph theory and have a couple of questions. 1) Can we always assume a graph is nonempty, i.e., if a graph $G$ has order $n$, do we assume $n\in \{1,2,...\}$? ...
82 views

Writing a proof of the convergence of a series defined recursively

Define the sequence $a_n$ recursively by $a_1=1$ and $$a_{n+1}=\frac13\left(a_n^2+\frac1n\right)$$ (a) Prove, by induction or otherwise, that $(a_n)$ is decreasing. (b) Prove that the series ...
48 views

Prove the inequality $(n+1)^4 < 4n^4$ for $n\geq 3$ by induction

The inequality I'm concerned with is $(n+1)^4 < 4n^4,\ n\geq 3$. I'm not sure how induction is supposed to work here. If I assume $(k+1)^4<4k^4$, I cannot see how this helps show ...
102 views

Factorial inequality $2!\,4!\,6!\cdots (2n)!\geq\left((n+1)!\right)^n$ using induction

I want to show $2!\,4!\,6!\cdots (2n)!\geq\left((n+1)!\right)^n.$ Assume that it holds for some positive integer $k\geq 1$ and we will prove, $2!\,4!\,6!\cdots (2k+2)!\geq\left((k+2)!\right)^{k+1}$. ...
106 views

Proving $\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{n}}>2-\frac{2}{n}$ by induction for $n\geq 1$

I have the following inequality to prove with induction: $$P(n): \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots\frac{1}{\sqrt{n}}>2-\frac{2}{n}, \forall n\in \mathbb{\:N}^*$$ I ...
441 views

Question on induction technique

When one uses induction (say on $n$) to prove something, does it mean the proof holds for all finite values of $n$ or does it always hold when even $n$ takes $\pm\infty$?
127 views

An exercise from Knuth's book - Proving a formula by induction

I would like to find a formula for this sum: $$\frac{1^3}{1^4+4} - \frac{3^3}{3^4+4} + \frac{5^3}{5^4+4} - ... + \frac{(-1)^n(2n+1)^3}{(2n+1)^4+4}$$ The answer given (Knuth's book, The Art of ...
52 views

Existence of two unrelated pairs in a constrained relation

Given two sets $S, T$ and a relation defined by a set of pairs $R \subset S \times T$, such that:  \exists \, s_1, s_2 \in S : s_1 \neq s_2 \\ \exists \, t_1, t_2 \in T : t_1 \neq t_2 \\ ...
67 views

Proving that a function is absolutely monotonic on a given interval

According to the following Wolfram Alpha article: http://mathworld.wolfram.com/AbsolutelyMonotonicFunction.html, the function $f(x) = -\ln(-x)$ is absolutely monotonic on the interval $[-1,0)$. My ...
33 views

Induction proof for $x \le y$

So these are $x \in \{1 ... i\}$ and $y \in \{ i + 1 ... n\}$, for $i, n \in \mathbb N$. I want to prove it for every $x \le y$. I know it`s easy but the solution is escaping me. I have tried with ...
97 views

Number of ways to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles

How many ways are there to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles? Rotating is allowed. Progress Let $T_n$ be the number of ways; then $T_n = T_{ n-1} + T_{ n-2} + 1$ ...
Suppose that we have a sequence of numbers $x_1,x_2,\ldots,x_n$ called $S$. A subsequence of $S$ is a sequence obtained by omitting some elements of $S$. An increasing subsequence of $S$ called $IS$ ...