Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [induction]

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

0
votes
3answers
36 views

Can i show instead of $n! \geq n^2$

Can i show instead of $n!\geq n^2$for $ n\geq4$ that $(n-1)! \geq n$ for $n \geq 4$?
2
votes
1answer
50 views

Lemma 2.2.3. For any natural numbers $n$ and $m$, $n + ( m{+}+)$ = $(n+m){+}+$: Analysis 1, Terence Tao

I'm self-learning real analysis using Terence Tao Analysis books. The book is very lucid. But in some cases Terence quickly go through the proof. And it becomes difficult for lesser mortals like us to ...
0
votes
2answers
24 views

Which n for base case if number defined on $\mathbb R$

I have the following task $S_n: (1 + x)^n \geq 1 + nx$ for every $x \in \mathbb{R}$ with $x > −1$ I am wondering which number to take for the base case in the inductive proof, because when I ...
2
votes
5answers
54 views

Proof by induction that $\frac13(n^3-n)$ is an integer. Am I on the correct path?

I have been trying to prove $$\frac{n^3-n}{3}=k\in \mathbb N $$ I have tried the following calculations, have however difficulties in the final step. Could you help me out? Here are my ...
-1
votes
2answers
43 views

How to prove by Principle of Induction? [on hold]

Prove by principle of induction that $$\frac{(2n)!}{2^n n!}$$ is odd for all $n\in\mathbb{N}$.
2
votes
6answers
51 views

Proof by mathematical induction that, for all non-negative integers $n$, $7^{2n+1} + 5^{n+3}$ is divisible by $44$.

I have been trying to solve this problem, but I have not been able to figure it out using any simple techniques. Would someone give me the ropes please? Prove for $n=1$ $7^3 + 5^4 = 968 = 44(22)$ ...
0
votes
2answers
12 views

Mathematical Induction proof with triangular number sequence w/ alternating positive and negative #'s

Consider the following five equations: 1) 1 = 1 2) 1 – 4 = -(1 + 2) 3) 1 –4 + 9 = 1 + 2 + 3 4) 1 –4 + 9 –16 = -(1 + 2 + 3 + 4) 5) 1 –4 + 9 – 16 + 25 = 1 + 2 + 3 + 4 + 5 Conjecture the ...
0
votes
0answers
50 views

Inductive proof for $3x+5y=n$ for $n\geq8$

The following problem is to be proven with induction: You want to buy some cats, but cats are only sold in batches of 3 or 5. Prove inductively that for any n ≥ 8, there is a way to purchase ...
5
votes
5answers
84 views

Recursive proof that $n^n \geq n!$

So I'm trying to prove, by induction, that $$ n^n \geq n!, \forall n\geq1$$ Base case: $$ \text{For } n=1, 1^1 = 1 \geq 1 = 1!$$ Hypothesis: $$ n^n \geq n!$$ Step: $$ \text{Trying to prove: } n^{...
0
votes
3answers
16 views

Prove by induction $2^n > 2n+1$ for all $n \geq 3$ [duplicate]

Base case $n=3$ - true Inductive Step Assume that for every $k \geq 3$, $2^k>2k+1$ show that $P(k+1)$ holds, that is show that $2^{k+1} > 2k+3$ $2^{k+1} = 2^k*2 > (I.H) (2k+1)*2 > (k+...
3
votes
2answers
80 views

What is the $n$-time iterated adjugate of an $n\times n$ matrix $A$?

What is $\underbrace{\text{adj}\Big(\text{adj}\big(\ldots(\text{adj}}_{n\text{ adj}}\ A)\ldots\big)\Big)$, where $\text{adj}$ is written $n$ times, and the order of the matrix $A$ is $n\times n$? Can ...
-1
votes
4answers
52 views

Prove by induction that $ 4^{2n}-3^{2n}-7 $ is divisible by 84 for all natural numbers.

Please, I have tried some methods of induction but I can't resolve. Sorry for my english. I cannot complete to prove. I haved factoring, dividing, adding new terms but i cannot avance for the second ...
0
votes
3answers
39 views

Prove by induction $n^2>7n+1$ for $n\geq8$

I am trying to prove the following by induction. $n^2>7n+1$ for all $n\geq8$ I have proved that the function works in the first possible case $$8^2>7(8)+1$$ $$64>57$$ Then subbed $k+1$ ...
0
votes
3answers
37 views

Prove $2\times1!+5\times2!+10\times3!+…+(n^2+1)n!=n(n+1)!$ for all positive integers

I am trying to prove by mathematical induction $2\times1!+5\times2!+10\times3!+...+(n^2+1)n!=n(n+1)!$ for all positive integers $n$. So far I have: Solved in the first case possible - $1$ Assumed ...
3
votes
2answers
43 views

Proof of $2^n > n$ by Induction

I'm new to induction and trying to prove $2^n > n$ for all natural numbers. I've seen a couple of examples but am confused about the the case going from $k = 1$ to $k =2$. So I show $2^1 > 1$ ...
0
votes
1answer
31 views

For a finite set of points $S$ in the plane: If line joining any two points in $S$ contains another point in $S$, then all points are collinear. [closed]

Prove, with mathematical induction, that for a countable finite set $S$ with points on a plane this holds: If on every line, defined with two points from $S$, lies at least one more point from $S$...
1
vote
0answers
53 views

Clarification of Answers given in Spivak's Calculus, Chapter 1-24

I am self-studying Spivak's Calculus. In Chapter 1, Question 24, $a_1 + \ldots + a_n$ is defined as $a_1 + (a_2 + (a_3 + \ldots + (a_{n-2} + (a_{n-1} + a_n))) \ldots )$. In part (a), we are asked to ...
0
votes
3answers
23 views

Induction proof verification?

Using induction, I have to prove that $n^2+n$ is divisible by 2. Here's how I did it, and I wanted to know if this is considered valid. I started with $(k+1)^2+(k+1)$, and after simplifying and ...
0
votes
2answers
25 views

Explaining the proof of Fibonacci number using inductive reasoning

Fibonacci numbers are defined as follows. $$F_{1}= F_{2} = 1$$ When $n \geq 3$, $$F_{n} = F_{n-1} + F_{n-2}$$ Task: Prove the following statement using mathematical induction: When $n \...
0
votes
0answers
14 views

A question related to induction and recursive sequences

I've been struggling with this problem for a long time now. It's Q2 part (b). Anyone have any ideas?Here it is
2
votes
1answer
33 views

regular language equality prove by induction

let $L\subseteq\{0,1\}^*$ be declared by the following conditions: a. $0, 01\in L$. b. if $w_1,w_2\in L$ so $w_1\cdot w_2\in L$. c. if $w\cdot 0\in L$ so $w \in L$. prove that $L=\{w| w=\epsilon\: ...
0
votes
4answers
26 views

Example of an assertion which is not true for any positive integer, yet for which the induction step holds.

Give an example of an assertion which is not true for any positive integer, yet for which the induction step holds. First of all, definition. In inductive step, we suppose that $P(k)$ is true ...
2
votes
2answers
52 views

Proving $\binom{n+1+m}{n+1}=\sum_{k=0}^m(k+1)\binom{n+m-k}{n}$

Use any method to prove that $$\binom{n+1+m}{n+1}=\sum_{k=0}^m(k+1)\binom{n+m-k}{n}$$ My Try: Base case: Let $m=1$ LHS$$\binom{n+1+m}{n+1}=\binom{n+2}{n+1}=(n+2)$$ RHS$$\sum_{k=0}^m(k+1)\binom{n+...
0
votes
1answer
32 views

Induction on powers of powers.

So I would like to prove that $ a_n \; | \; a_{n+1} - 2 $, where $a_n = 6^{2^n} + 1 $ Now I know I need to do this by induction and so I begin by showing this is true for the base case. (Proposition)...
0
votes
0answers
44 views

Sum of quadratic series [duplicate]

I just found out that $$\sum _{i=0}^n\:i^2= \frac{n\left(n+1\right)\left(2n+1\right)}{6}$$ and $$\sum _{i=0}^n\:i^3 = \frac{n^2\left(n+1\right)^2}{4}$$ but I don't understand how did we get the ...
0
votes
1answer
33 views

Recurrence proof by induction

I'm having a hard time to understand how am i supposed to solve this question: $T(n) = \sqrt{n}T(\sqrt{n})+n$. Prove by induction that $T(n) = \Theta (n \log{(\log{(n)})})$. These are all the data ...
4
votes
2answers
45 views

Algebraic proof that $\binom{n+k-1}{k} = \sum\limits_{i=0}^k \binom{(n-1)+(k-i)-1}{k-i}$

Prove (algebraically) that $$f_k(n) = \binom{n+k-1}{k} = \sum\limits_{i=0}^k \binom{(n-1)+(k-i)-1}{k-i} = \sum\limits_{i=0}^k f_{k-i}(n-1)$$ for $n \geq 2$ and that $f_k(1) = 1$ for all $k$. Then, ...
-1
votes
0answers
51 views

Prove that $a^{2^n}$ is divisible by $4 * 2^n$

Prove that $a^{2^n}-1$ is divisible by $4 * 2^n$ for $a \in Z$, $n\in Z$ where $a$ is an odd number. I am trying to solve this question using simple induction. Currently getting very stuck on the ...
0
votes
0answers
24 views

Proof Ideas - Strong Induction, Pascal's Triangle and Fibonacci Numbers

I'm looking for attributes/characteristics/properties to prove about Pascal's Triangle or the Fibonacci numbers. Preferably something that requires a strong induction proof that is on the same level ...
0
votes
5answers
31 views

Help with a proof by induction on polynomial roots

I am currently studying induction. I understand the how the principle is supposed to work, I can follow and understand a proof by induction quite fine (the ones I've seen anyway), but actually using ...
1
vote
2answers
15 views

Summation equivalence

I am having trouble seeing how this summation equivalence holds true: $\sum_{i=0}^\infty x^i$ = $\frac{1}{1-x}$ if |x| < 1 The only thing I can see where there would be a problem is if x = 1 or ...
0
votes
2answers
30 views

Prove $x \geq 2$ implies $x^{n} \geq 2^{n}$

Prove $x \geq 2$ implies $x^{n} \geq 2^{n}$. By induction. Clearly it holds for $n = 1$ by the assumption. Now assume $x \geq 2$ and $x^{k} \geq 2^{k}$ for some $k \in \mathbb{N}$. Then combine ...
-3
votes
2answers
37 views

Proof by induction; For each natural number $n$, the function$ x^n +x^{n−1} +…+x+1$ is continuous.

I am very frustrated, and I can't figure out the induction step. After proving the induction basis for when n=0.
1
vote
1answer
38 views

Induction with two variables in PA

This probably has been asked before, but apologies, I don't know how to locate it. I want to prove $\forall x,y: P(x, y)$. My premises are: $$P(0, 0) \wedge \\ [\forall x: P(x, 0)] \wedge \\ [\...
0
votes
0answers
21 views

Problems to demonstrate a succesion of sets

The exercise seems easy but i have problems to resolve it: We define a succession of sets: $$\begin{align} A_k &= \{\{m \in \mathbb N | m < n\} | n \in \mathbb N, n \le k\} (\text{for each } ...
1
vote
0answers
28 views

How to normalize Dirichlet distribution?

The Dirichlet distribution is defined as: $$ p(\vec{\mu}_M|\vec{\alpha}_M) = c(\vec{\alpha}_M) \Pi_{k=1}^M\mu_k^{\alpha_k-1} $$ where $\vec{\mu}_M, \vec{\alpha}_M$ is a vector of length $M$ and $\sum_{...
2
votes
1answer
35 views

Use complete induction to prove that $a_n < 2^n$ for every integer $n \geq 2$

Define the sequence of integers $a_0, a_1, a_2, \cdots$ as follows $$ a_i = \begin{cases} i+1 & 0 \leq i \leq 2 \\ a_{i-1} + a_{i-2} + 2a_{i-3} & i > 2 \\ \end{cases} $$ ...
1
vote
1answer
50 views

How to incorporate induction into the logic system?

Before I begin the question, it is meant to generalize to other theories, but I will focus on the natural numbers theory, with the following peano axioms: The question is, could the induction schema ...
1
vote
0answers
97 views

Prove that Dyck language is subset of grammar

last two days I am trying to prove, that Dyck language $L$ over the alphabet $\{[, ]\}$ is a subset of the language $L(G)$ generated by the grammar with rules $\{S \rightarrow [S]S | \epsilon \}$. ...
1
vote
3answers
54 views

Prove by induction $7^n$ is an odd number for every natural number n

I have proved the base case already of n=1 where $7 = 2p+1$ Then I assumed $n=k$ for $7^k = 2p+1$ for $k \in N$ and $p \in N$ To prove $7^{k+1} = 2p+1$ I have these steps so far: $7(7^k) = 2p+1$ ...
3
votes
1answer
57 views

Explain this derivative identity: $ \frac{1}{2^n} \frac{d^n}{dy^n} \frac{(1+y)^{2n+3}(1-y)}{((1+y)^2 -2yx)^2} \bigg|_{y=0} = (n+1)! x^n $

I have the following result that I believe to be true: $$ \frac{1}{2^n} \frac{d^n}{dy^n} \frac{(1+y)^{2n+3}(1-y)}{((1+y)^2 -2yx)^2} \bigg|_{y=0} = (n+1)! x^n $$ The LHS is something that arose in ...
0
votes
1answer
32 views

Prove if $s<x$ and $t<z$, then $st<xz$. [closed]

Assuming $s,t,x,z$ are natural numbers, if $s < x$ and $t < z$, then $st < xz$. Prove this. Do I need induction? Please help. I am very confused. Thank you.
0
votes
1answer
49 views

Show there are $2^n$ forms a $n \times n$ matrix can take, preferably via Pascal's triangle

Where "a form" for some RRE matrix is its description in terms of the number of all-zero rows it has and the position of pivots in the non-zero rows. I've tried using induction, the base case is ...
3
votes
3answers
19 views

Proof by Induction Question including Rational Numbers

I just recently covered 'rational numbers' in class and was assigned the following question to solve using induction for n, so that for all $q \in \mathbb{Q}$ \ {1}:...
0
votes
5answers
42 views

combination numbers induction proof

Consider numbers $n \geq r \geq 1$ where $n,r \in \mathbb{Z} $, prove the following: $$\binom {r}{r} + \binom {r+1}{r}...+ \binom n r = \binom {n+1}{r+1}$$ Only thing I know is that if I choose to ...
0
votes
1answer
39 views

Proof by induction using functions

Prop: If the set $A$ is infinite then there exists an injective function $z:N→A$. $z$ is defined inductively, for the base case, explain how it is plausible to define$ z(1)$. Now suppose that $z(1),z(...
0
votes
1answer
48 views

Proofs involving functions and induction

Prop: If the set $A$ is infinite then there exists an injective function $z : ℕ → A$. $z$ is defined inductively, for the base case, explain how it is plausible to define $z(1)$. Now suppose that $z(1)...
0
votes
2answers
49 views

How many cases do I need for a proof by induction

First of all, English is not my mother tongue so I'm sorry if my definitions or concepts aren't explained correctly. I just started a discrete math course and we started with induction, the professor ...
1
vote
1answer
36 views

Is there a name for this method of proof?

If I want to prove that some statement $P(n,m)$ is true for all $n, m \in \mathbb{N}$, I can do this by showing that: $P(1, 1)$ $\forall n \in \mathbb{N}: P(1, n) \implies P(1, n+1)$ $\forall n, m \...
2
votes
1answer
27 views

Proving $n \leq 3^{n/3}$ for $n \geq 0$ via the Well-Ordering Principle

I'm attempting to prove: $$n \leq 3^{n/3} \quad \text{for }n \geq 0$$ I'm having a little trouble continuing. This is what I have so far: Suppose for a contradiction there is a subset of ...