Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

0
votes
1answer
13 views

Expanding Base 2B representation of an integer

Consider an integer$L$ written in Base 2B which digits $$a_n a_{n-1} a_{n-2} ... a_1 B$$ Where $a_i$ are arbitrary constants such that $9 \le a_i < 2B$. I am attempting to prove that the square ...
4
votes
2answers
102 views

After Round Robin, there is always a player such that every other was either beaten by him or beaten by a player beaten by him

Every participant of a tournament plays with every other participant exactly once. No game is a draw. After the tournament, every player makes a list with the names of all the players, who either were ...
-11
votes
2answers
335 views

How can I show that by induction?

I have asked that question - Dividing square of 2013x2013 - and I receive useful answer, which was correct, of course, but because solution of that exercise is my homework I have to have an accurate ...
0
votes
3answers
90 views

Inductive proof that $n^3+2n$ is divisible by $3$ for every integer $n$ [closed]

I have to prove this property with an inductive explanation If $n \ge 1$ and is an integer, then $3$ divides $n^3+2n$
2
votes
1answer
60 views

Prove that $\sqrt{n} \le \sum_{k=1}^n \frac{1}{\sqrt{k}} \le 2 \sqrt{n} - 1$ is true for $n \in \mathbb{N}^{\ge 1}$

I'm trying to solve these induction exercises proposed by the department of mathematics of Oxford University. I don't know how to give a valid proof for the third one which says the following: ...
2
votes
1answer
162 views

Proving that $\,\sqrt [n] n < 1 + \sqrt{\frac{2}{n}}\,$ for all positive $n$

Hello I am having difficulty proving the following inequality: $$ \sqrt[n]{n} < 1 + \sqrt{\frac{2}{n}} \quad \text{for all positive integers}\,\,\, n. $$ I am trying to use mathematical induction ...
1
vote
0answers
34 views

A sequence defined as $a(n)=n-a(a(n-1))$ $n\geq 1,\ a(0)=0$, how to prove that $a(n)=⌊(n+1)(-1+√5)/2⌋$

$a(n)=n-a(a(n-1)), \ n \geq 1,\ a(0)=0$, to prove that $$ a(n)=⌊(n+1)\cdot \frac{\sqrt{5} - 1}{2}⌋. $$ This is an exercise of "Discrete Mathematics and Its Application".(Supplementary exercise 72 of ...
3
votes
4answers
59 views

Elementary Proof of sum of alternating factorials

so I came across the rather interesting identity $$ \sum_{i = 0}^{\infty}\left[\sum_{j=0}^{i}\left[\frac{(-1)^j}{j!} \right] \prod_{j=0}^{i}\left[ (x-j)\right] \right] = x! $$ For positive integers ...
8
votes
2answers
47 views

How to prove an inequality

$a$, $b$, $c$, $d$ are rational numbers and all $> 0$. $\max \left\{\dfrac{a}{b} , \dfrac{c}{d}\right\} \geq \dfrac{a+c}{b+d}\geq \min \left\{\dfrac{a}{b} , \dfrac{c}{d}\right\}$ Hope someone ...
0
votes
3answers
383 views

Proving by mathematical induction: $1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+…+\frac{1}{\sqrt{n}}>2(\sqrt{n+1}-1)$ [duplicate]

Possible Duplicate: Proof of an inequality: $\sqrt{n} < \frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \cdots + \frac{1}{\sqrt{n}}$ Proving ...
3
votes
1answer
274 views

Use induction to prove that $ 1 + \frac {1}{\sqrt{2}} + \frac {1}{\sqrt{3}} … + \frac {1}{\sqrt{n}} < 2\sqrt{n}$

Use induction to prove that $ 1 + \frac {1}{\sqrt{2}} + \frac {1}{\sqrt{3}} ... + \frac {1}{\sqrt{n}} < 2\sqrt{n} $ My attempt was as follows: Lets assume the inequality is true for n = k $S_k ...
4
votes
1answer
74 views

how to solve this elementary induction proof: $\frac{1}{1^2}+ \cdots+\frac{1}{n^2}\le\ 2-\frac{1}{n}$

this is a seemingly simple induction question that has me confused about perhaps my understanding of how to apply induction the question; $$\frac{1}{1^2}+ \cdots+\frac{1}{n^2}\ \le\ 2-\frac{1}{n},\ ...
0
votes
1answer
49 views

Help to clarify inductive step for proof of $\mathbb{N_m} \rightarrow \mathbb{N}_n\Rightarrow m\le n$

The statement to prove is: If there exists an injection $\mathbb{N_m} \rightarrow \mathbb{N}_n$ then $m\le n$ The solution says to prove by induction on $n$. I just need help on the inductive ...
1
vote
4answers
210 views

Mathematical Induction (summation): $\sum^n_{k=1} k2^k =(n-1)(2^{n+1})+2$

I am stuck on this question from the IB Cambridge HL math text book about Mathematical induction. I am sorry about the bad formatting I am new and have no idea how to write the summation sign. Using ...
1
vote
1answer
775 views

Sets induction problem (complement of intersection equals union of complements)

Let $n\ge 2$ and $A_1,\dots,A_n$ be sets in some universe $S$. In this problem we will give a proof by induction of the identity $$\left(\bigcap_{i=1}^nA_i\right)^c=\bigcup_{i=1}^nA_i^c\;.$$ ...
1
vote
1answer
37 views

Proving properties of closures using intersection of indexed sets and topology

How would I write a proof for this example? Let X be a set, and let $B \subseteq \mathcal P \left({X}\right)$. Define $B^* =${ $U \subseteq X:$ There is an index set $I$ and $U_{i} \in B$ for each ...
2
votes
1answer
16 views

Uniqueness in transfinite recursion.

Theorem of transfinite recursion: Given a well-ordered set $A$ let $\varphi(g,y)$ be a ZF formula such that for every $a \in A$ and every function $g$ with domain $I_a$ (where $I_a$ is the initial ...
1
vote
2answers
50 views

If $a_i>o$ then $(a_1a_2\cdots a_{2^n})^{1/2^n}\leq \frac{a_1+a_2+\cdots+a_{2^n}}{2^n}$

I need help to prove this inequality, I have no idea how to proceed with the inductive step: $$a_1,a_2,\ldots,a_{2^n}>0 \Longrightarrow(a_1a_2\cdots a_{2^n})^{1/2^n}\leq ...
1
vote
1answer
27 views

Sum of nth powers and generalized polynomial sum

So this is a 2-part question (both parts I believe are closely related): How exactly does on express the sum $$\sum_{i=0}^{k}{i^n} = Q(n,k)$$ in a closed form For arbitrary positive integers ...
0
votes
5answers
49 views

Proof of $\forall n \in \Bbb N$, $n > 2 \implies n! < n^n$

What I've got so far is this: Base case: n = 3 then $3 *2 * 1 = 6$ and $3^3 = 27$ $\therefore 6 < 27, 3! < 3^3$ So the base case is true. So if we assume $n! < n^n$ (n > 2) $(n + 1)! = ...
1
vote
4answers
41 views

Prove $\forall n \in\Bbb N$, $0 < a < 1$ $\implies$ $a^n \leq 1$

I'm trying to prove this by induction but I'm running into some trouble. The base case is $0$, so, $a^0 = 1$, the inequality holds true Being new to induction, I don't exactly know what to do for ...
1
vote
1answer
31 views

Can someone explain the logic behind this step in a induction problem

There is a question in the book that I don't quite understand. Question Show that $n^2$ is smaller than $2^n$ whenever $n\ge5$. At the $k+1$ step it gets very whacked and confusing. $k+1$ ...
1
vote
1answer
36 views

Prove by Structural induction, circular permutations

Prove by Structural Induction: For a circular permutation of $n$ elements, the number of permutations is $(n-1)!$ How is this done?
0
votes
2answers
39 views

How do I reduce this induction problem at the k+1 step

Show that $2^n > n^2$ through induction and so far I got to the $k+1$ step, but I am stuck. I have $2^{k+1} = 2 +2^k$, but I don`t know how the book turned it into $k^2 +k^2$. The book then ...
2
votes
5answers
3k views

Simple Proof by induction: “9 divides $n^3 + (n+1)^3 + (n+2)^3$”

I'm trying to prove using induction that 9 divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a non-negative integer. So far, I have: Base case: P(1) = (1) + (8) + (27) = 36, 36 can be divided by 9 ...
2
votes
2answers
72 views

Better proof that $n \leq 2n$ for all natural numbers?

I tried proving via induction on naturals that $n \leq 2n$ for each natural $n$. Obviously, $0 \leq 2(0)$, and then assuming for any given $n$, $n \leq 2n$, you just show that $n + 1 \leq 2(n + 1).$ ...
4
votes
1answer
94 views

How to prove Post's Theorem by induction?

The proof of post's theorem is given in my textbook in two pages of explanation using a non-induction method. I was told that ,using induction on length of the proof, one can get a simpler and more ...
1
vote
2answers
70 views

Proving inequality $3^{n^2} > (n!)^4$

Prove that $3^{n^2} > (n!)^4$ for all positive integers $n$. I tried to use induction on this problem but failed to do so. I instead tried to prove $3^{2n+1}>(n+1)^4$, but couldn't come up ...
0
votes
1answer
30 views

Induction proof involving sets

Suppose $A_1,A_2,...A_n$ are sets in some universal set $U$, and $n\geq2$. Prove that $\overline{A_1 \cup A_2 \cup ... \cup A_n}$ = $\overline{A_1} \cap \overline{A_2} \cap ... \cap \overline{A_n}$
0
votes
2answers
52 views

Proof by induction $\sum_{k=1}^{n}$ $k \binom{n}{k}$ $= n2^{n-1}$ for each natural number n [duplicate]

Prove by induction that $\sum_{k=1}^{n}$ $k \binom{n}{k}$ $= n2^{n-1}$ for each natural number n
1
vote
1answer
62 views

Proof by induction or strong induction [closed]

I have to prove the following using induction or strong induction Suppose $a\in\mathbb{Z}$. Prove that $5 | 2^na$ implies $5 | a$ for any $n\in\mathbb{N}$.
0
votes
3answers
80 views

Lightbulb puzzle related to proofs by induction.

The puzzle question was as follows: There is a circle of $n > 2$ lights with a switch next to each of them. Each switch can be flipped between two positions, thereby triggering the on/off states of ...
2
votes
1answer
74 views

Mathematical Induction proof for $(n!)^2 > n^n$

I have the math problem (induction proof - $n!^2 > n^n$) that I try to solve and I haven't yet managed to get it right so maybe somebody could help me. My current plan solving the problem is the ...
2
votes
2answers
21 views

Proving arithmetic series by induction

How do I prove this statement by the method of induction: $$ \sum_{r=1}^n [d + (r - 1)d] = \frac{n}{2}[2a + (n - 1)d] $$ I know that $d + (r - 1)d$ stands for $u_n$ in an arithmetic series, and the ...
4
votes
2answers
224 views

Prove the principle of mathematical induction in $\sf ZFC $

How does one prove the principle of mathematical induction using the standard axioms of $\sf ZFC $?
1
vote
1answer
238 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
7
votes
10answers
2k views

Prove by induction that $5^n - 1$ is divisible by $4$.

Prove by induction that $5^n - 1$ is divisible by $4$. How should I use induction in this problem. Do you have any hints for solving this problem? Thank you so much.
1
vote
2answers
43 views

Number of ways to write a natural as a sum of naturals [duplicate]

Problem: Let $n$ be a natural number, and $S(n)$ be the number of ways $n$ can be written as a sum of naturals. For instance, $S(3) = 4$ because $3 = 2+1 = 1+2 = 1+1+1$ and these are four different ...
3
votes
2answers
83 views

Prove by induction that $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ is decreasing

I want to prove that the following sequence is monotonously decreasing: $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ I think it should be ...
1
vote
3answers
67 views

Infinite descent method and strong induction

I encountered the following statement of the infinite descent principle (PID): PID. Let $p(n)$, $n \in \mathrm{N}$, be an arbitrary property of natural number $n$. Assume that (e) $p(1)$ is ...
0
votes
1answer
137 views

Proof completion: if $Y$ is a closed term in strong nf, then $Yx$ weakly reduces to a strong nf $Z$

I am self-studying Hindley & Seldin's Lambda-Calculus and Combinators. I would appreciate some help with filling in a final detail for a proof for the following statement regarding combinatory ...
14
votes
3answers
1k views

What makes induction a valid proof technique?

What makes induction (over natural numbers) a valid proof technique? Is $$ \dfrac{ P(0) \quad \forall i \in \mathbb{N}. P(i) \Rightarrow P(i+1) }{ \forall n \in \mathbb{N}. P(n)} $$ just taken for ...
3
votes
0answers
66 views

Can I use the equality $\phi^2=\phi+1$ without proving it?

I am looking at the following exercise: $$\text{ Show with induction,that the } i^{th} \text{ number Fibonacci satisfies the equality: } $$ $$F_i=\frac{\phi^i-\hat{\phi}^i}{\sqrt{5}}$$ where $\phi$ ...
4
votes
5answers
544 views

Proving that $f(n)$ is an integer using mathematical induction

I want to prove that $$\frac{n^3}{3}+\frac{n^5}{5}+\frac{7 n}{15}$$ is an integer for every integer $n \geq 1$. I define P(n) to be: $$\frac{n^3}{3}+\frac{n^5}{5}+\frac{7 n}{15}$$ is an integer. ...
7
votes
4answers
272 views

The largest integer less than $n$ is $n-1$

Let $n$ be a positive integer. Prove that the largest integer which is less than $n$ is $n-1$. Attempt of a solution: Since $n$ is a positive integer $n>0$. I think I have to use the well-ordering ...
0
votes
1answer
39 views

Inductive proof of inequality $a\le ab$ for nonnegative integers

I reading about of proof of the claim "If $a \ge 0$ and $b > 0$, then $a \le ab$. (Here $a$ and $b$ are integers.) The proof the author is employing is inductive. I understand the basis case; ...
1
vote
0answers
58 views

Prove: $a^m\cdot a^n \cdot a^p=a^{m+n+p}$

How can I prove the following: Prop.: let be $m,n,p \in \Bbb{N}$ and $a \in \Bbb{R}$ then $$a^m\cdot a^n \cdot a^p=a^{m+n+p}$$ ??? I thinked by induction and I must prove: 1) $a^0\cdot a^0 \cdot ...
0
votes
1answer
57 views

am i cheating in this number theory proof?

the question (from burton's elementary number theory); $verify\ that\ \forall n\ge 1,$ $$2\cdot6\cdot10\cdots(4n-2)=\frac{(2n)!}{n!}$$ my work/proof; this is obviously true for $n=1$, so assume ...
0
votes
2answers
44 views

Prove that $n<(3/2)^n$ for any $n$ with induction [closed]

need help with induction with inequality, I suck at it. $n<\left(\frac{3}{2}\right)^n$ for any $n$
-1
votes
1answer
21 views

Inductive Proof Algorithm

so I'm working on an algorithms assignment and am having a tough time understanding what to do: The equation is: $$T(n) = 2T(n/4) + n = \Theta(n) = O(n)$$ Right now I have gotten this far: $$T(1) = ...