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

learn more… | top users | synonyms

1
vote
1answer
33 views

Using induction to show associativity on $x_1+\dots + x_n$

I want to use induction to show that the sum $x_1 + \dots + x_n$ of real numbers is defined independently of parentheses to specify order of addition. I know how to apply induction(base, assumption, ...
2
votes
2answers
46 views

Proving with induction $(1-x)^n<\frac 1 {1+nx}$

Prove using induction that $\forall n\in\mathbb N, \forall x\in \mathbb R: 0<x<1: (1-x)^n<\frac 1 {1+nx}$ My attempt: Base: for $n=1: 1-x<\frac 1 {1+x}\iff 1-x^2<1$, true since ...
1
vote
2answers
46 views

Show if $0 \le a <b$ implies $0 \le a^{\frac{1}{n}}<b^{\frac{1}{n}}$

Given that $0\le a<b$ show that $0\leq a^{1/n}<b^{1/n}$ Is this proof by induction? Show it's correct for $n=1$ Assume true for $n=k$, then $0\leq a^{1/k}<b^{1/k}$ holds for some $k$, ...
1
vote
3answers
60 views

Use induction to prove that sum of the first $2n$ terms of the series $1^2-3^2+5^2-7^2+…$ is $-8n^2$.

Use induction to prove that sum of the first $2n$ terms of the series $1^2-3^2+5^2-7^2+…$ is $-8n^2$. I came up with the formula $\displaystyle\sum_{r=1}^{2n} (-1)^{r+1}(2r-1)^2=-8n^2$ but I got ...
0
votes
0answers
11 views

Proof for Determinants using Laplace and induction.

Matrix $A = (a_{ij}) \in M (n x n, Field)$, Matrix $B = ((-1)^{i+j}a_{ij})$ I need to prove that det(A)=det(B). I thought induction might be one solution, but I don't know how to apply the Laplace ...
1
vote
2answers
37 views

Induction proof concerning Pell numbers

Problem: The Pell numbers $p_n$ are defined by the recurrence relation \begin{align*} p_{n+1} = 2p_n + p_{n-1} \end{align*} for $n \geq 1$, together with $p_0 = 0$ and $p_1 = 1$. Prove with ...
0
votes
1answer
20 views

summation inequality with logarithms

show: $$\sum_{i=1}^n \log_{2}\,i = O(n\log n)$$ Proof by induction: $$\sum_{i=1}^n \log\,i \le n\log n$$ $$\text{Test for n=1: }\sum_{i=1}^1 \log_{2}\,i \le 1\log 1$$ $$0 \le 0\text{ true for ...
3
votes
1answer
81 views

How is induction justified in intuitionistic logic?

This question might be extremely naïve for which I apologise in advance. The induction principle can be stated as: If $A ⊂ ℕ$ such that $1 ∈ A$, and $ν(A) ⊂ A$ (where $ν\colon ℕ → ℕ$ is ...
0
votes
1answer
37 views

For what natural number $n$ is the following inequality true: $2^n \geq 2\cdot n^2$?

Can you solve this by using induction? The inequality is true for $n = 1$, but is false until $n = 7$. After the induction step I got $$2^n \geq n^2 + 2n + 1.$$ If you take the limit as $n$ ...
0
votes
0answers
18 views

Practicing mathematical proofs in preparation for another course and could use some help [on hold]

I'm starting a course on Algorithms and the professor wants to test our induction and proof knowledge. Problem is, our prerequisite courses never focused on such material. I'm hoping someone could ...
3
votes
1answer
52 views

Proof that $\sum_{i=1}^n{1} = n$ for all $n \in \Bbb Z^+$

It seems obvious that $$\forall n \in \Bbb Z^+, \sum_{i=1}^n{1} = n $$ However, I'm having trouble coming up with a formal proof for this. Given a concrete number like $4$, we can say that ...
1
vote
1answer
12 views

Power of two commuting elements in a group is the binary operation of each of the two elements raised to that power

Let $(G,\ast)$ be a group and let $n\in\aleph$. Prove that if g, h $\in G$ commute, then $(g\ast h)^n$=$g^n\ast h^n$
0
votes
1answer
25 views

Proving the existence of a Bijection between Cartesian Products of Sets by Induction

Prove by induction that for any sets $A_1, \ldots , A_n$, there is a bijection from $(((A_1 \times A_2) \times A_3) \times \ldots \times A_n)$ to $A_1 \times (A_2 \times ( \ldots (A_{n-1} \times A_n) ...
0
votes
2answers
27 views

proof by induction summation inequality

show by induction that: $$\sum_{i=1}^n i^2 = O(n^3)$$ what I have so far: $$\sum_{i=1}^n i^2 <= n^3$$ base case: for n=1 $$\sum_{i=1}^1 i^2 <= 1^3$$ ...
0
votes
1answer
11 views

Cantor Set and Base 3 Decimal Expansions

I'm trying to show that every point in the Cantor Set (obtained by "middle-thirds" removal, starting with $[0,1]$) has a base 3 decimal expansion consisting of only zeros and twos. I think the proof ...
1
vote
1answer
12 views

Proof via strong induction of a string output

I'm still new to the whole proof thing (first class of discrete mathematics and analysis right now). I could do general induction problems, but the fact that 'n' is the output here along with the ...
1
vote
1answer
26 views

Proof of the second principle of mathematical induction

This was an exercise in my lecture notes for which no answer was provided, so I seek verification on whether my proof is correct. Prove that if 1. $P(n_0)$ is true for some $n_0 \in \mathbb N$, and ...
1
vote
1answer
24 views

Inverse of a product in a group can be written as the product of the inverses of each element in reverse order

Let $(G,\circ)$ be a group and let $g_1,...,g_n\in G, n\in\aleph$. Prove that $(g_1\circ ...\circ g_n)^{-1}=g_n^{-1}\circ ...\circ g_1^{-1}$ I tried this by induction but was unsure how to take out ...
0
votes
1answer
41 views

prove by mathematical induction

I've been trying to solve this but I'm having trouble in simplifying it, in order to match the right hand side. Could you solve this? $$\sum_{i=1}^{n+1} i\cdot 2^i = n\cdot 2^{n+2} +2 ,$$ for all ...
0
votes
3answers
76 views

Proof of an inequality by induction

Let $n \in \mathbb N^+$. Show that if $x_1, x_2, ... , x_n$ are $n$ real numbers such that $-1 \le x_i \le 0$ for each $1 \le i \le n$, then $$(1 + x_1)(1 + x_2)...(1 + x_n) \ge 1 + x_1 + x_2 + ... + ...
3
votes
2answers
35 views

Proving $1+\sum_{i=1}^n i (i!)=(n+1)!$ [duplicate]

How would you prove the following using induction. n is a non negative integer $$1+\sum_{i=1}^n i i!=(n+1)!$$ This be what I did base case let $n=3$ $$1+1+4+18=(3+1)!$$ $24=24$ Hypothesis step ...
2
votes
1answer
22 views

Height of quasi-complete binary tree

Let us define a quasi-complete binary tree as a rooted binary whose nodes have all two children except at most those of the penultimate level, which can have either one or two children. I read that ...
3
votes
1answer
42 views

How to prove that calculating Ackermman function stops?

Let $$\begin{eqnarray*} A(0,y) &=& y+1 \\ A(x+1,0) &=& A(x,1) \\ A(x+1,y+1) &=& A(x,A(x+1,y)) \end{eqnarray*}$$ be Ackermann function. How to prove by structural induction ...
0
votes
0answers
18 views

What is the difference between assuming for $\forall k< n$ and proving for $n$ than assuming for $n$ and proving for $n+1$

What is the difference between assuming for $\forall k< n$ and proving for $n$ than assuming for $n$ and proving for $n+1$ (or $n-1$ and proving for $n$)? both with induction. The first one is ...
2
votes
3answers
54 views

Proof by induction, binomial coefficient

I have to make the following proof: $${\sum\limits_{k=1}^n}{k}{n\choose k} = n2^{n-1}$$ Base case, $n = 1$: $${\sum\limits_{k=1}^{1}}{k}{1\choose k} = 1 = 1\cdot2^0=1$$ Inductive Hypothesis: for ...
0
votes
4answers
45 views

I'm having trouble understanding a step of induction.

The problem my teacher presented was to prove, $(1 + x)^n \geq 1 + nx$ for all real numbers $x > -1$ and integers $n \geq 2$. The way it was done in class is: $(1+nx)(1+x) ≤ (1+x)^n (1+x) $ ...
-1
votes
1answer
24 views

Ordering of real numbers compatible with n-th powers/reciprocal powers (induction)

I have to use induction to prove that $$0 \leq a < b \implies 0 \leq a^n < b^n$$ for all natural n. Also (perhaps very similarly) that $$0 \leq a < b \implies 0 \leq a^{1/n} < b^{1/n}.$$ ...
1
vote
5answers
104 views

how to prove: $\sum\limits_{k=1}^n k\binom{n}{k}=n \cdot 2^{n-1} $ [duplicate]

need help to prove this: $\sum\limits_{k=1}^n k\binom{n}{k}=n \cdot 2^{n-1} $ where $n$ is integer $\geq 1$. Question also said taking the derivative of $(1 + x)^n$ would be helpful which I've found ...
0
votes
0answers
24 views

Geometric interpretation or solution of an induction problem

Problem: Suppose you begin with a pile of $n$ stones and split this pile into $n$ piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile, ...
0
votes
1answer
21 views

Two recurrence relations gcd proof

Let $q_1, q_2,\ldots$ be a sequence of integers with $q_i\gt0$ for all $i\gt 1$. Define $(a_n)_{n\ge-1}$ and $(b_n)_{n\ge-1}$ by the following recurrence relations: $a_{-1}=0,\ a_0=1,\ b_{-1}=1,\ ...
0
votes
3answers
41 views

simple proof by induction exercise - beginner

I am rather illiterate when it comes to mathematics, I am afraid. In an effort to change that, I grabbed a copy of 'What is mathematics? : An elementary approach to ideas and methods' and have already ...
0
votes
2answers
40 views

Trouble solving this induction problem

Show that, for every $n\ge2$, $3^n >n(n-1)$. Well, I started by showing the base case ($n = 2$): $3^2 > 2$ Now, for $n+1$: $P(n)\Rightarrow P(n+1)$ $$3^{n+1} > (n+1)n$$ My ...
-2
votes
0answers
57 views

Prove by induction the $n$th derivative [closed]

Let $f(x) = \ln(1+x)$. Prove by induction that, for $n \geq 1$, $$ f^{(n)}(x) = (-1)^{(n-1)}\cdot \frac{(n-1)!}{(1+x)^n}. $$ How do I go about proving this? I have done the n=1 base step to show it ...
0
votes
1answer
45 views

proof of the negative binomial series using induction?

$$(1-x)^{-n} = \sum_{k\ge0}{k+n-1 \choose n-1}x^k$$ I'm supposed to prove this for any integer n $\ge$ 1 via induction on n. Base case where n = 1 is easy enough to prove, but what about the ...
1
vote
7answers
50 views

Induction proof of $1 + 6 + 11 +\cdots + (5n-4)=n(5n-3)/2$

I need help getting started with this proof. Prove using mathematical induction. $$ 1 + 6 + 11 + \cdots + (5n-4)=n(5n-3)/2 $$ $$ n=1,2,3,... $$ I know for my basis step I need to set $n=1$ but I ...
1
vote
1answer
19 views

Bernoulli's inequality variation

To prove: $(1+a_1)(1+a_2)\ldots(1+a_n)\geq\dfrac{2^n}{n+1}(1+a_1+a_2+\ldots+a_n)$ when $a_i\geq1$ This seems to be based on Bernoulli's Inequality (which can be proved by induction). Trying the ...
0
votes
2answers
48 views

If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$

Suppose that $k$, $n$, and $d$ are integers and $d$ is not $0$. Prove: If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$. You may not use the theorem stating the following: Let ...
2
votes
4answers
62 views

Proof By Induction Help? [closed]

I've been working through proof by induction and i'm stuck on this question. Can somebody provide some help? $$\huge 2^n-1=\sum_{i=0}^{n-1}2^i\text{ for }n\ge 1$$
0
votes
2answers
27 views

Proof of well ordering principle for the set of positive integers with directly using the principle of induction and not strong induction

Can we prove well ordering principle for the set of natural numbers (positive integers ) with directly using the principle of induction i.e. $( S \subseteq \mathbb N ,1 \in S \space \&\ n \in S ...
3
votes
2answers
80 views

Proof by Iteration

It seems that I suffer the "too-much-logic-too-pedantic-too-confused"-disease. (You know? This very disease which lets you doubt everything and lets you yell for formalized proof. It's annoying, ...
1
vote
4answers
53 views

Induction profe with geometrical cycle

I have an equation: $$x(n+1)=5x(n)+4\\x(0)=0$$ For my task I need to provide simple equation for $x(n)$, so I go for this method: I make some changes in equation: $$x(n+1)=5x(n)+5-1\\ ...
0
votes
3answers
73 views

Prove by induction that $G(n)=2G(n-1)$ [closed]

I have a task to solve with algorithm, which is writing all the binary numbers. I wrote the recurrence relation below, as I count the few first values: $$G(n) = \begin{cases}1&\qquad n = 0\\ 2G(n ...
1
vote
1answer
38 views

Proof By Induction Using Binomial Coefficients

I'm having a really hard time with this proof by induction: Prove this formula by induction: $1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}$. Easy enough, right? Wrong. I have to do it using ...
2
votes
2answers
79 views

Prove $1^3 + 2^3 + \cdots + n^3 = (1 + 2 + \cdots + n)^2$ using Induction [duplicate]

Prove $1^3 + 2^3 + \cdots + n^3 = (1 + 2 + \cdots + n)^2$ using Induction My proof so far: Let $P(n)$ be $1^3 + 2^3 + \cdots + n^3 = (1 + 2 + \cdots + n)^2$ Base Case $P(1):$ LHS = $1^3 = 1$ ...
1
vote
1answer
42 views

What is wrong with the following argument involving Fibonacci and Lucas numbers?

The Lucas numbers $L_n$ are defined by the equations $L_1 = 1$, and $L_n = F_{n+1} + F_{n-1}$ for each $n \geq 2$. What is wrong with the following argument? Assuming $L_n = F_n$ for $n = ...
0
votes
1answer
37 views

Proof by induction - summation inequality

Prove by induction for $d,n \in \mathbb{Z}^+$ that $$ \sum_{k=0}^{n}d^{k}\geq \frac{(n+1)^{d+1}}{d+1}. $$ The base case for $n = 1$ makes $1 \geq 1$ which passes. Then I found that $$ ...
0
votes
1answer
57 views

On proving a statement is true by induction

We prove $\sum_{i=1}^{n} x^3 = (1+2+\cdots+n)^2$. We observe that this expression is true for $ n=1$. Now assume this is already true; we prove it for $\sum_{i=1}^{n+1} x^3 = (1+2+\cdots+n+n+1)^2$. We ...
4
votes
3answers
56 views

Proving $ n! \geq 2^{n-1} $

Prove that $$ n! \geq 2^{n-1}$$ for $n \geq 1$. My initial solution by induction goes like this. For $n = 1 : 1 \geq 1 $. Assuming that $$ n ! \geq 2^{n-1}.$$ Then for $n+1$, $$ (n+1)! = ...
-1
votes
1answer
42 views

Induction - Prime Numbers [duplicate]

Prove that, for every natural number $n > 2$, there is a prime number between $n$ and $n!$. [Hint: There is a prime number that divides $n! - 1$.]
3
votes
3answers
51 views

Mathematical induction involving inequalities and congruences

I have the following two problems: "Prove each of the following statements by induction for all positive integers $n$:" $2\cdot7^n \equiv 2^n\cdot(2+5n) \bmod 25 \quad$ <-- I have been going at ...