Stack Exchange Network

Stack Exchange network consists of 175 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 questions about induction over natural numbers but is also appropriate for other kinds of induction such as transfinite, structural, double, backwards, etc.

0
votes
0answers
10 views

Proving the number of internal nodes of a binary tree

Let $T$ be a nonempty 2-3 tree, so that it includes at least one node. Prove that if $T$ represents a subset $S\subseteq E$ such that $|S|= n\in \Bbb N$, then $T$ has at most $n-1$ internal nodes. I ...
0
votes
0answers
31 views

Strong induction

I have this question, Prove, $7 + 77 + 777 +7777 + 77...$n digits..$77 = 7/81[(10^n × 10) - 9n - 10]$ By induction. Now since this question was given in the exercise that involves proving various ...
2
votes
2answers
41 views

Two dimensional induction

I have the following problem: I need to prove that given the following integral $\int_{0}^{1}{c(k,l)x^k(1-x)^l}dx = 1$, we the constant $c(k,l) = (k+l+1) {{k+l}\choose{k}} = \frac{(k+l+1)!}{k!l!}$, ...
-2
votes
2answers
42 views

Proof of Binomial-coefficients sum [duplicate]

How could I show by induction that this sum is true? $${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+...+{n \choose n}^2 = {2n \choose n}$$ All help is appreciated!
0
votes
0answers
21 views

Property takagi function by induction.

In a lecture on Applied Functional Analysis, the professor showed us some properties of the Takagi function from this paper. He wrote at the end the following property and said it could be easily done ...
-1
votes
1answer
36 views

Proving the first principle of mathematical induction

I was asked to prove the first principle of mathematical induction without using the well ordered principle. If someone can elucidate the steps clearly it would be a great help ! Thank you!
2
votes
1answer
26 views

What is a good example of prefix induction?

the Wikipedia article for Mathematical induction introduces a few variations of the classic principle, such as the strong induction. The strong induction comes with a few examples, namely the closed ...
0
votes
3answers
33 views

How to show that $(n!/n^n)_{n\geq 0}$ is a null sequence?

How to show that $\left(\frac{n!}{n^n}\right)_{n\geq 0}$ is a null sequence, meaning it tends to zero. i tried proving that $n^n\geq n!$ for $n\in \mathbb{N}:n>0$. Is that a correct method? Base ...
0
votes
1answer
41 views

Prove by induction that, for all $n\in\Bbb N$, $\sqrt{n} ≤ \sum_ {k=1}^n \frac{1}{\sqrt{k}} < \sqrt{n} + \frac{n}{\sqrt{n+1}}$.

So, I know that for my base case I use $n=1$, and that for the inductive hypothesis we assume the pattern holds until the $n-th$ iteration. Then use that to prove the $(n+1)-th$ iteration ($\Bbb P(n)\...
1
vote
6answers
55 views

Prove $5^n + 3^n - 2^{2n+1} > 0$ by induction

I am not sure how to deal with the $-2^{2n+1}$ term. I did the basis proof for n=1 I am stuck at this step: $$ 5^{k+1}+3^{k+1}-2^{2(k+1)+1} = 5\cdot 5^k + 3 \cdot 3^k -2^3 \cdot 2^{2k} $$ Any ...
1
vote
3answers
37 views

Prove by mathematical induction that $\sum_{i=0}^n (2i-1)^2 = \frac{n(2n+1)(2n-1)}{3}$

One of my homework problems is to prove that $\sum_{i=1}^n (2i-1)^2 = \frac{n(2n+1)(2n-1)}{3}$ I already completed the basis step $[2(1)-1]^2 = 1 $ $\frac{(1)[2(1)+1][2(1)-1]}{3} = 1$ Then I ...
0
votes
1answer
76 views

Is there an error in this proof the the “strong induction” theorem? Is this Escherian logic?

By set predicates, I mean the "tests for inclusion" used in defining sets. That may be more of a computer scientific than mathematical use of the the term predicate. I included predicate logic in ...
1
vote
4answers
67 views

Mathematical induction proof $n^4-1$ is divisible by $16$ for all odd integers $n$

I'm stuck towards the end of proving this, here's my attempt: $P(3) = 80/16 = 5$, True $P(k) = k^4-1$ $P(k+1)= (k+1)^4-1$ Expanded $= k^4+4k^3+6k^2+4k+1-1$ This is where I am stuck at. Sorry for ...
0
votes
1answer
17 views

Is induction the correct approach here?

Let $a_1, a_2, \dots, a_n$ (real numbers) be such that $$a_1 - a_2/3 + \dots + (-1)^{n - 1}a_n/(2n - 1) = 0.$$ Prove that $$f(x):= a_1\cos(x) + a_2\cos(3x) + \dots + a_n\cos([2n - 1]x) = 0,$$ for ...
1
vote
2answers
66 views

Strange Proof: The Principle of Mathematical Induction implies that 1 is the least positive natural number.

I have just begun using Judson's 2018 Abstract Algebra: theory and applications. In the text, there is a Lemma with the following statement and proof: The Principle of Mathematical Induction implies ...
0
votes
5answers
30 views

what's the best way to prove the equivalences of such formulas?

I want to prove the following: $$2^n+2^{n-1}+...+2^1 + 1 = 2^{n+1}-1$$ The only Method that I know of is proof-by-induction but is this the best way to prove the equivalences of such formulas?
2
votes
4answers
49 views

How to prove De Moivre's theorem inductively [duplicate]

It is given that $(\cos\theta + i\sin\theta)^n = \cos n\theta + i\sin n\theta$ where $n\in Z^+$. I can show it works for $n=1$ but I am stuck in showing it inductively. I have got as far as below but ...
-5
votes
1answer
20 views

Using PMI prove $(n+3)^2 \leq 2^n+3$ [on hold]

Want an answer to this question fast I have tried a lot but cannot find a solution
0
votes
1answer
38 views

How to prove that for index i all the following n sums are positive?

Given are $n$ real numbers $x(1)$, $x(2)$, ..., $x(n)$. Some of them are positive, some may be negative. The total sum is positive. Prove the following statement: There exists some index $i$ such ...
2
votes
3answers
57 views

How to get sum of $\frac{1}{1+x^2}+\frac{1}{(1+x^2)^2}+…+\frac{1}{(1+x^2)^n}$ using mathematical induction

Prehistory: I'm reading book. Because of exercises, reading process is going very slowly. Anyway, I want honestly complete all exercises. Theme in the book is mathematical induction. There were ...
1
vote
1answer
46 views

I don't understand one line in problem to prove $|2^S| = 2^{|S|}$

Problem to prove by induction: If $ S $ is a finite set, then $\vert 2^S \vert = 2^{\vert S \vert}$ Proof: Induction on size of $S$, call it $n$ , $n \ge 0$. Base case: Suppose $n=0$. Now, $|2^S| =...
0
votes
2answers
46 views

How to prove that $ n < n! - 1 $ for $n > 2.$? [closed]

How to prove that $ n < n! - 1 $ for $n > 2.$? I have tried it by induction but I got stucked in the induction step in proving $ n +1< (n + 1)! - 1 $ for $n + 1> 2$. Could anyone help ...
2
votes
2answers
39 views

Inductive Proof of Group with Prime Decomposition is Isomorphic to Direct Product of Cyclic Groups

My lecturer set as a bonus exercise the following induction proof: If $G$ is a finite abelian group $|G| = p_1^{n_1} \cdots p_s^{n_s}$ is the decomposition of $|G|$ into a product of distinct prime ...
1
vote
1answer
23 views

Let $P(n)$ be : the sum of the first odd natural numbers equal $n^2$. Express in summation notation and use induction.

I presented the first odd $n$ natural integers as $2n+1=n^2$. In summation notation I just factored this into $(n-1)(n-1)$. I am unsure whether this is correct and also I don't know how to carry out ...
0
votes
2answers
52 views

Let $a$ be a natural number not divisible by $5$

Let $a$ be a natural number not divisible by $5$ Prove that $8a^{8n}+a^{4n}-4$ is a multiple of $5$ for all n natural number. My try : Using induction Let : $ A=8a^{8n}+a^{4n}-4$ For n=0 then ...
1
vote
1answer
29 views

Self-complementary graph with 4k+1 vertices, which is 2k-regular [duplicate]

Prove that ∀k∈N, k≥1, there is a self-complementary graph with 4k+1 vertices, which is 2k-regular. I think that the best way to prove it is by induction. Any helpful suggestions? (I know that this ...
1
vote
1answer
33 views

Question about self-complementary graphs

Question Prove that for every integer k≥1, exists a self-complementary graph with 4k vertices half of which are of degree 2k-1 and the other half of degree 2k. My approach So, I think the easiest way ...
0
votes
2answers
30 views

proof by mathematical induction (n)!< (n)^n

"Let P(n) be the statement that (n)! < (n)^n, where is an integer greater than 1. Prove by mathematical induction that P(n) is true for all integers n greater than 1." I've written Basic step ...
0
votes
1answer
32 views

A divisibility problem with mathematical induction

Prove by mathematical induction that if $k$ is odd and $n$ is a natural number, then $2^{n + 2}$ divides $k^{2n} - 1$. I'm stuck while assuming $n = q$ is true as hypothesis, as I can't prove for $q +...
1
vote
1answer
31 views

Confused on an algebraic step of inductive proof

The part I've boxed is what is throwing me - why is it 6(k+1) instead of 6(k+1)^2?
-1
votes
0answers
35 views

Proving inequality by induction [closed]

How to prove by induction? Given: a,b are constants and (a+b>0) Prove: a^n+b^n≥(a+b)^n/2^(n−1)
1
vote
1answer
30 views

Equalities with sum of squares

Does anyone have an idea about the following exercises? I have tried both of them by using induction, but I haven't got it. Prove that for every $k\in{\mathbb{N}}$, if $4k=m_1^2+\dots m_{3+k}^2$ with ...
1
vote
1answer
76 views

Why is the definition of inductive set well defined?

I've been studying from Enderton's Mathematical Introduction to Logic in which he defines an inductive set as follows: To simplify our discussion, we will consider an initial set $B \subseteq U$ ...
0
votes
2answers
38 views

Prove that $\sum_{i=1}^{2^n} \frac{1}{i} \geq 1 + \frac{n}{2}$ holds for all $n$

I know that: $$\sum_{i=1}^{2^{n+1}} \frac{1}{i} = \bigg( \sum_{i=1}^{2^{n}} \frac{1}{i} \bigg) + \bigg( \sum_{i=1}^{2^{n}} \frac{1}{2^n + i} \bigg)$$ But I can't seem to establish this by induction:...
1
vote
1answer
30 views

Congruences and second-order recurrence relations

I'm having trouble tackling this ghastly exercise. Let $(a_n)_{n\in\mathbb{N}}:a_1=3,a_2=-1,a_{n+1}=a_{n+1}+4^{2n}a_n+15^n n^{15}$. Prove that $a_n \equiv 3^n \pmod 5$. I know that every term in ...
2
votes
4answers
83 views

Prove that for all $n \in \mathbb{N}$, either 3 or 13 divides $3^n + 13n^2 + 38$

Let $a\in \{3,13\}.$ I'm having trouble with this proof. I know that $$3^{n+1} + 13(n+1)^2 + 38 = (3^n + 13n^2 + 38) + (2\cdot 3^n + 26n + 13)$$ But I can't prove that $a \mid 2\cdot3^n + 26n + 13$. ...
-2
votes
0answers
24 views

Proof by mathematical induction about n^3 [duplicate]

proof by mathematical induction that, for all n equals N, 1^3+2^3+3^3+...+n^3=(n(n+1)/2)^2
2
votes
0answers
38 views

Recursion-like sequences which are hard to relate recursively

Consider the sequence \begin{align*} a_1&=1\\ a_2&=2+\sqrt1\\ a_3&=3+\sqrt{2+\sqrt1}\\ &\kern5.5pt\vdots\\ a_n&=n+\sqrt{n-1+\sqrt{\cdots+\sqrt{1}}}. \end{align*} ...
0
votes
2answers
42 views

I'm actually lost regarding inductions [duplicate]

Basically, it's what it says in the title, could someone solve step by step this induction? It would be even better with an expanation for said steps, but it's not all that needed, I want to read the ...
0
votes
0answers
41 views

Find a simple formula for a sum [duplicate]

I need find a simple formula for an exercise, and I really don't know how to approach. I think that the solution invloves induction but I really don't know how to start. The sum is: $$\frac{1^3}{1^...
1
vote
7answers
2k views

Why can't I prove summation identities without guessing?

In order to prove using induction that $$\sum_{k = 1}^n k = \frac{n(n+1)}{2}$$ I have to first guess what the sum is and then show that this guess bears out using induction. This is very unusual ...
1
vote
2answers
70 views

Prove by induction on $n$ that $(1)(2)+(2)(3)+…+n(n+1)={1\over 3}n(n+1)(n+2)$

So after testing myself with this question, I was unable to solve it. I was able to prove the base case $n=1$, but I was pretty lost on the induction step. I took a look at the solution and here it is:...
2
votes
2answers
32 views

Proof by induction: $\sum_{j=1}^{n-1}{j^k}<\frac{n^{k+1}}{k+1}$ with $n,k \in \mathbb{N}$ and $n\geq 2$

Proof by induction: $\sum_{j=1}^{n-1}{j^k}<\frac{n^{k+1}}{k+1}$ with $n,k \in \mathbb{N}$ and $n\geq 2$ Inductive step: $$\sum_{j=1}^{n}{j^k}<\frac{(n+1)^{k+1}}{k+1}$$$$\Bigg(\sum_{j=1}^{n-1} j^...
0
votes
2answers
37 views

Proof by induction: $\sum^{2n-1}_{i=1} (2i-1)=(2n-1)^2$

$\sum^{2n-1}_{i=1} (2i-1)=(2n-1)^2$ I get stuck after proving the base case is true. Usually with induction I assume the left and right sides are equal at some k, but I'm not sure how to approach ...
1
vote
1answer
36 views

Prove that $(1+x)^n>1+nx$ for all integers $n\geq2$, where $x>-1$ and $x\neq0$.

I would like to get feedback on whether this proof is valid or not and would like to know if my usage of set-builder notation is correct. I get the feeling that the discrete mathematics class I'm in ...
1
vote
0answers
37 views

For all $n\in \mathbb{N}$, find the values for$\big( \sum_{i=1}^{n} (-1)^i i! \big) \mod 36$

I did some calculations and found out that for $n=1,2,3,4$ the remainders are $35,1,31,19$ respectively. From then on I conjectured that the remainder was always 7. I then attempted to prove this by ...
1
vote
1answer
24 views

n choose k proof with mathematical induction

I'm reading "what is Mathematics" written by Richard Courant. I'm trying to do all the exercises. It's really not easy for me, even though exercises are really easy. For now I'm trying to solve n ...
5
votes
3answers
194 views

Are there “interesting” theorems in Peano arithmetic, that only use the addition operation?

More precisely, are there "interesting" theorems of Presburger arithmetic, other than the following four well-known "interesting" ones? The commutativity of addition. The theorem stating there are ...
1
vote
1answer
45 views

Prove that for every $n\geq6$ the equation $1/a_1^2 + … 1/a_n^2 = 1$ has answer in $\mathbb{Z}$

Prove that for every $n \geq 6$ the equality $1/a_1^2 + ... 1/a_n^2 = 1$ has answer in $\mathbb{Z}$ (I mean it has an answer where all $a_i \in \mathbb{Z}$) (Repetition is allowed) After some testing ...
0
votes
2answers
25 views

Base case for $\sum_{j=1}^{n-1}{j^k}<\frac{n^{k+1}}{k+1}$ with $k\in \mathbb{N}$ and $n\geq 2$

Base case for $\sum_{j=1}^{n-1}{j^k}<\frac{n^{k+1}}{k+1}$ with $k\in \mathbb{N}$ and $n\geq 2$ Do I have to use $k_0=1$ and $n_0=2$? I am a little confused since that's what I can come up with:$$j^...