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

learn more… | top users | synonyms

2
votes
1answer
271 views

Help with induction proof for formula connecting Pascal's Triangle with Fibonacci Numbers

I am in the middle of writing my own math's paper on the topic of Pascal's Triangle. During the investigation I have came up with a formula for counting elements of Fibonacci Sequence using the ...
0
votes
1answer
39 views

Inductive Proof Recursive Definition

Using this recursive Definition: $$a_{n} = \left\{\begin{matrix} 4 & n=1\\ a_{n-1}+4n-5 & n \geq 2 \end{matrix}\right.$$ I somehow have to prove using induction $$a_{n} = 2n^{2} - ...
0
votes
1answer
58 views

Fibonacci Proof with Induction [duplicate]

$$f(n) = \left\{\begin{matrix} 0 & n=1\\ 1 & n=2\\ f_{n-1} + f_{n-2} & n\geqslant 2\end{matrix}\right.$$ How can I prove by induction that $$f_{n} \geq \left ( 1.5 \right )^{n-1}$$ ...
2
votes
2answers
83 views

Fibonacci Proof Using Induction

$$f(n) = \left\{\begin{matrix} 0 & n=1\\ 1 & n=2\\ f_{n-1} + f_{n-2} & n\geqslant 2\end{matrix}\right.$$ How can I prove by induction that $$f_{n} \leq \left ( \frac{1+\sqrt{5}}{2} ...
2
votes
1answer
116 views

Fibonacci proof by induction

I have fibonacci numbers defined as such: $$ f(n) = f(n-1) + f(n-2)$$with$$ f(0) = 0 $$$$f(1) = 1$$ I have to prove that $$ F(n) \geq 1.5^{n-1}, n \geq 6$$ Base Case: $$ f(6) = 8 \geq (1.5)^5 ...
0
votes
3answers
59 views

Divisibility proof by induction.

$ 169$ | $3^{3n+3}-26n-27$ ? Fulfilled for $n=0$. Induction to $n+1$: An integer $x$ exists so that $ 169x= 3^{3n+6}-26n-27-26$ $ 169x= 27*3^{3n+3}-26n-27-26$ $ 169x= 26*3^{3n+3}+3^{3n+3}-26n-27-26$ ...
0
votes
3answers
47 views

Induction summation proof: $\sum_{i=1}^{n} \frac{4}{5^{i}} < 1$

Don't want a full answer but can somebody help me in the right direction with this problem. Have to prove using induction $$\forall n \geqslant 2: \sum_{i=1}^{n} \frac{4}{5^{i}} < 1$$
2
votes
0answers
64 views

My first proof employing strong induction / complete induction (very simple number theory). Please mark/grade. [duplicate]

What do you think about my first proof employing strong induction? What mark/grade would you give me? Theorem Every natural number greater than 1 is a product of one or more primes. Proof First, ...
0
votes
1answer
32 views

Composition of linear maps and induction

With DonAntonio's help Composition of linear maps. I managed to find $t^4 = t^2 +4(t^2- id)$ , $t^6 = t^2 + 4(4+1) (t^2 -id)$ and $t^8 = t^2 + 4 ( 1+ 4 +4^2)(t^2 -id) $ So now I want to prove it ...
18
votes
3answers
868 views

My first induction proof (very simple number theory). Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
1
vote
1answer
99 views

Can't find an identy for proving that $ \sum_{k=0}^{i+1} \binom {i+1} k=2^{i+1}$ [duplicate]

$$ \sum_{k=0}^{i+1} \binom {i+1} k$$ I can't find an identity for this summation :( To clarify I'm trying to prove using induction that this sum is equal to $2^{i+1}$, I have my basis and ...
0
votes
1answer
28 views

Prove that all elements in the set T is divisible by 3 using structural induction.

Let T be the set defined recursively as follows: (1) (0,3) $\in$ T (2) If (x, y) $\in$ T, then (x + 2, y - 1) $\in$ T and (x - 3, y) $\in$ T. (3) Every element of T can be obtained from (1) by ...
1
vote
0answers
75 views

Proof by induction on contraction mapping?

Let $k:[0,1] \times [0,1] \to \mathbb{R}$ be continous, and $x(t) = \int_0^t k(t,s)x(s)ds$ for $0 \leq t \leq 1$. Not let $Tx(t) = \int_0^t k(t,s)x(s)ds$ and suppose $sup_{0 \leq t, s \leq 1}|k(t,s)|= ...
0
votes
3answers
71 views

Prove by mathematical induction that $d^k \equiv 1 \pmod{2}$ for all $k$ when $d$ is odd

Let $d \in N $ be an odd integer. Prove by induction that: $\forall k \in N$ , $d^k$ = 1 (mod 2). How do I begin this question? I have a hard time understanding what to do for the inductive step. ...
0
votes
10answers
1k views

How to prove for each positive integer $n$, the sum of the first $n$ odd positive integers is $n^2$?

I'm new to induction so please bear with me. How can I prove using induction that, for each positive integer $n$, the sum of the first $n$ odd positive integers is $n^2$? I think $9$ can be an ...
0
votes
0answers
96 views

How to use two types different forms of induction to prove stamp problem?

For this problem I have to prove using two different types of induction to show that using only 3 cent stamps and 5 cent stamps, any postage amount 8 cents or greater can be formed. Using the two ...
0
votes
0answers
115 views

Proving this property of a tournament graph by induction?

I am working on practicing proofs by induction. Can you please take a look at the proof below and tell me if I proved it correctly? I am particularly worried about the inductive step. Definition ...
0
votes
1answer
242 views

How can I prove prime factorization theorem by induction?

The prime factorization including both existence and uniqueness. I have totally no idea about this problem except the basecase. In this problem we only consider number greater or equal to 2. So the ...
1
vote
4answers
448 views

prove that a power of odd number is always odd by induction.

The problem has confused me for like half hour. An integer is odd if it can be written as d = 2m+1. Use induction to prove that the ${d^n}$ = 1 (mod 2) by induction, the basecase is pretty simple , ...
0
votes
1answer
176 views

Cayley's formula for the number of trees(Recursion)

I'm trying to understand the proof by recurcion and induction for the Cayley's formula for the number of trees.While I'm trying to understand it there are some things that I don't get at all. -It ...
1
vote
5answers
165 views

How to prove that $n^5 - n$ is a multiple of $5$? [duplicate]

Hello I'm new to induction so please bare with me. For this problem I have to use induction to prove: For every integer $n\geq 1$, the number $n^5 − n$ is a multiple of $5$. Can someone please help me ...
1
vote
1answer
65 views

How would I solve this mathematical induction proof? I am stuck after the first part of the induction. [duplicate]

$$1 + 5 + 5^2 + \ldots + 5^n = \frac{5^{n+1}-1}{4}$$ Basis case $n= 0$: $1^0 = 1 \;\;\;\;\;\;\;\;\;\;\;\; \frac{5^{1+1}-1}{4}=1$ Assume true for $n=k$: $$1 + 5 + 5^2 + \ldots + 5^k = ...
0
votes
3answers
54 views

proving golden ration with induction

If $\displaystyle a=\frac{1+\sqrt{5}}{2}$ and $\displaystyle b=\frac{1-\sqrt{5}}{2}$, prove that $\displaystyle f_n=\frac{a^n-b^n}{\sqrt{5}}$ for all $n\in\mathbb{P}$ Would we start with a base case ...
2
votes
2answers
67 views

Proving an inequality using induction

Use induction to prove the following: $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{2^n}\geq1+\frac{n}{2}$ What would the base case be? Would it still be $n=0$ so ...
1
vote
4answers
98 views

Proof by induction that $n^2 \ge n$ for all $n \in \mathbb{Z}$

Prove that the inequality $n^2\geq n$ holds for every integer. With induction, I believe we would start with the base case, that is $n=0$ $n=0$ $0^2 \geq 0$, which is true. Then would I start with ...
3
votes
2answers
79 views

Help finishing proof via induction for a summation

So I have to prove the following equation using induction for n >= 2: $$ \sum\limits_{i=1}^n 4/5^i < 1 $$ However the question asks me to prove something stronger such as this: $$ ...
0
votes
2answers
54 views

What is the easiest way to prove by induction?

Is there any easy way to do this? I get the basic step.. where you prove it for some number.. but I don't get the induction step. Do you literally take the given equation that you just proved with ...
1
vote
4answers
76 views

Principle of mathematical induction problem

Prove the inequality $4^{2n}>15n$ For $n = 1$, $4^{2\cdot1}=16>15\cdot1$ Let us assume it is true for $n=k$ $4^{2k}>15k$
2
votes
1answer
67 views

When is there an $m$ that divides $u^{an+b}+v^{cn+d}$ for all $n$

This is a generalization of Prove by induction? which asks how to prove that $73$ divides $8^{n+2}+9^{2n+1} $for all $n$. Here is my generalization: Find conditions on positive integers $u, a, v, c$ ...
1
vote
1answer
34 views

Is this divisibility proof by induction correct/sufficient?

To show: 13 | $4^{2n+1}+3^{n+2}$ I used induction beginning successfully with n=0 (or n=1), then making the step to n+1: An x exists so that $13x = 4^{2n+3}+3^{n+3}$ $13x = 16*4^{2n+1}+3*3^{n+2}$ ...
0
votes
6answers
104 views

Prove by induction?

The problem asks to prove $8^{(n+2)}+9^{(2n+1)}$ is divisible by 73 Proof by induction: we look at base case $n=1$ => which gives us $1241$ which is divisible by $73$; now for $n+k$ we know that ...
1
vote
1answer
81 views

Proof by induction: $2^n > n$

Base is $2^1 > 1$. Now we assume $2^n > n$ and try to obtain $2^{n+1} > (n+1)$. If I can use $2^n > 1$, I could just add that to $2^n > n$ and get $2^{n+1} > (n+1)$ but I don't ...
2
votes
1answer
152 views

Prove by induction on $n$ that any set of $n$ reals is bounded

Prove by induction on $n$ that any set of $n$ reals is bounded Working: I approached the problem by splitting it into three cases and proving each case, it seems a bit tedious to me how I did it, so ...
1
vote
0answers
579 views

Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs

I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ...
2
votes
3answers
86 views

How can I prove $2^n > n^2 $ by induction using a basis $> 4$ [duplicate]

I've been trying to prove this statement by induction; however, in following the steps I normally take I end up utterly stuck. I know that I must be missing something, but I have been stuck on this ...
0
votes
1answer
44 views

Proof by induction of the value of $3^n$ modulo 10

I am learning proof by induction in my math class and I am having trouble with this problem: Prove that for $k \in N, 3^{4k-3}\equiv 3 \pmod{10}, 3^{4k-2} \equiv 9 \pmod{10}, 3^{4k-1} \equiv 7 ...
2
votes
5answers
156 views

Help with proof using induction: $1 + \frac{1}{4} + \frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$

I am having trouble with the following proof: For every positive integer $n$: $$1 + \frac{1}{4} + \frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$$ My work: I have tried to add ...
2
votes
1answer
97 views

Proving divisibility by using induction: $133 \mid (11^{n+2} + 12^{2n+1})$ [duplicate]

If $n > 0$, then prove the following by using induction: $$133|(11^{n+2} + 12^{2n+1}).$$
0
votes
2answers
43 views

Induction for a sequence starting with a negative and ending with a positive number.

Prove by induction on n that for any $n \ge 2$, any sequence of non-zero real numbers $a_1, a_2, \dots, a_n$ that starts with a negative number (meaning $a_1 < 0$) and ends with a positive number ...
2
votes
3answers
143 views

Proof that $\binom{ n}{k} \in \mathbb N$

This problem is from Spivak. Give another proof that $\binom{n}{k}$ is a natural number by showing that $\binom{n}{k}$ is the number of sets of exactly $k$ integers each chosen from $1, \ldots,n$. I ...
0
votes
1answer
54 views

Using induction to prove $\sum\limits^n_{k=1} 9^k = 0.5 \cdot \sum\limits^{2n}_{k=1} (-1)^k \cdot 3^{k+1}$

$$\sum^n_{k=1} 9^k = 0.5 \cdot \left[\sum^{2n}_{k=1} (-1)^k \cdot 3^{k+1}\right]$$ I have tested both with a python script and it seems to be correct. For the life of me, I am unable to unwind the ...
0
votes
0answers
52 views

Taylor series like polynomials

Let $U$ be an open subset of $R^n$ and $f:U\rightarrow \mathbb{R}$ a function and $x\in U$ such that in a small neighbourhood of $x$ and for $\epsilon \in \mathbb{R^b}$ sufficiently small we have the ...
0
votes
2answers
334 views

[Beginner]How to tackle mathematical proofs?

So I recently joined university for a BSc in mathematics. I have never been exposed proofs but I have knowledge of algebra, trigonometry, and some differentiation/integration. Now I'm struggling with ...
1
vote
4answers
202 views

Induction proof of $n^{(n+1) }> n(n+1)^{(n-1)}$

The question statement from my homework booklet goes: Prove by mathematical induction that $n^{n+1} > n(n+1)^{n-1}$ is true for all integers $n \geq 2$. I've managed to come up with this ...
1
vote
1answer
88 views

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

Prove, disprove, or give a counterexample: $$\sum_{i=0}^n \left(\frac 3 2 \right)^i = 2\left(\frac 3 2 \right)^{n+1} -2.$$ I went about this as a proof by induction. I did the base case and ...
0
votes
1answer
49 views

Understanding math behind proof relating to binary search trees (issue with logarithms)

I am posting the entire problem starting with the initial theorem since it is pertinent to the final solution. There are two things I don't understand here. In the inductive case, why does it ...
0
votes
1answer
63 views

Mathematical Induction proof that $\sum\limits_{i=1}^n \frac{1}{i^2} < 2 - \frac1n$ [duplicate]

I am to use mathematical induction to prove: $$\sum_{i=1}^n\frac{1}{i^2}<2 - \frac{1}{n}$$ my base case is n = 3: LHS: $\frac{1}{1}+\frac{1}{4}+\frac{1}{9}= \frac{49}{36}$ RHS: ...
1
vote
3answers
80 views

prove combinatorical identity using induction

Question: prove by induction on $n+m$ the combinatoric identity: $$\sum_{k = 0}^n {m + k \choose k} = {m + n + 1 \choose n}$$ I've tried to do on both $n$ and $m$ but I think it isn't the right way. ...
0
votes
2answers
110 views

Prove $(1 - a)^n \geq 1 - na$ for $0 < a < 1$

This is exercise problem from "The Art of Computer Programming - Fundamental Algorithm". Prove by induction that if $0 < a < 1$, then $(1 - a)^n \geq 1 - na$ Here is my attempt: If n = ...
6
votes
1answer
331 views

Prove that $\,\sqrt [n] n < 1 + \sqrt{\frac{2}{n}}\,$

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 but I ...