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
2answers
20 views

Prove that a recurrence relation (containing two recurrences) equals a given closed-form formula.

Prove that $a_n = 3a_{n-1} - 2a_{n-2} = 2^n + 1$ , for all $n \in \mathbb{N}$ , and $a_1 = 3$ , $a_2 = 5$ , and $n \geq 3$ Basis: $a_1 = 2^1 + 1 = 2 + 1 = 3$ $\checkmark$ $a_2 = 2^2 + 1 = 4 + 1 = 5$ ...
5
votes
5answers
54 views

Demonstration of sum of powers of $2$ [duplicate]

Theorem : For every natural number $p$: $$\sum^p_{i=0} 2^i = 2^{p+1}-1$$ I trieed to demonstrate the theorem using induction Demonstration : $1)$ If we have $p=0$ then we get $2^0=2^{0+1}-1$ that is ...
4
votes
5answers
88 views

Proving a Statement using Mathematical Induction

I'm trying to prove that $6 \mid (n^3 - n)$ where $n$ is a nonnegative integer. I started off by proving the basic step with $P(6)=4$. The next step would be the induction. However I'm having a bit f ...
3
votes
3answers
46 views

Prove this inequality.

Let $S=a_1+...+a_n<1$ where $a_i>0$. Prove that $1+S<(1+a_1)\cdot ... \cdot (1+a_n)<{1\over 1-S}$. I started with the right inequality but I am not sure it iss plausible (I did something ...
1
vote
0answers
20 views

Proving with a given definition that if $|A|=|B|$ then $A,B$ are equivalent (with induction but without using the induction hypothesis)

Let $A,B$ be finite sets, we'll say the sets are equivalent if $|A\setminus B|=|B\setminus A|$. Prove with the above definition that if $|A|=|B|$ then $A,B$ are equivalent. Suppose ...
0
votes
3answers
53 views

Inductive step in proof of Freshman's Dream

I am trying to prove that for $K$ a field of characteristic $p$ prime, $q$ a power of $p$ and $x,y$ in $K$, $$(x+y)^q=(x^q + y^q).$$ I have the base case, and now I am trying to do the inductive ...
3
votes
3answers
50 views

Proving that two summations are equivalent [duplicate]

Give a constructive proof to show that for all $n \geq 1$ , $\sum\limits_{i=1}^n i^3 = (\sum\limits_{i=1}^n i)^2$ Observe that $(n+1)^4 - n^4 = 4n^3 + 6n^2 + 4n + 1$ . Now, the two following ...
2
votes
1answer
23 views

Use induction to show $a_n$ is no greater than $4\log_2(\log_2(n))$

Given a sequence where $a_1 = 1$ and $a_n = 1+ a_{\lfloor\sqrt{n}\rfloor}, n\geqslant 2$. Show that $a_n \leqslant 4\log_2\log_2(n), \forall n \geqslant 3$. Here's my idea: Base case is $n=3, a_3 = ...
1
vote
2answers
38 views

Proof of Binomial Formula Summation - Induction

Let $n\geq 1$ be an integer. Prove that $$ \sum_{k=1}^n k\binom{n}{k} = n\cdot 2^{n-1}. $$ Not sure how to go about doing this question. It says that finding the derivative of $(1+x)^n$ is useful. ...
1
vote
1answer
35 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
49 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
48 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
61 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
38 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
19 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
56 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
26 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
30 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
13 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
28 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
42 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
23 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
44 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
55 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
48 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
121 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 ...
2
votes
2answers
44 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
43 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
42 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 ...
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
20 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
49 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
81 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\\ ...
1
vote
3answers
77 views

Prove by induction that $G(n)=2^n$ [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 ...