Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

0
votes
0answers
100 views

max number of keys in a 2-3-4 tree

Let $M(L)$ be the largest number of keys (a $2$-node has $1$ key and two children, a $3$-node has $2$ keys and $3$ children, and a $4$-node has $3$ keys and $4$ children) in a $2-3-4$ tree that ...
2
votes
1answer
132 views

Fibonacci Sequence Exercise

I need some help checking the following solution. The Fib sequence is defined by $a_1 = 1, a_2 = 1$ and for all $n\geq 2$, $a_{n+1} = a_n + a_{n-1}$. Thus, the sequence begins: 1, 1, 2, 3, 5, 8, ...
0
votes
4answers
282 views

Induction: Show that $\sin(2x) + \sin(4x) + \ldots+ \sin(2nx) = \frac{\sin(nx)\sin((n+1)x)}{\sin(x)}$

Show that $\sin(2x) + \sin(4x) + \ldots+ \sin(2nx) = \dfrac{\sin(nx)\sin((n+1)x)}{\sin(x)}$ I tried to use induction. Base case is easy, but I'm stuck at the induction step (from $k$ to $k+1$). ...
3
votes
2answers
276 views

Prove $\frac{1}{2} + \cos(x) + \cos(2x) + \dots+ \cos(nx) = \frac{\sin(n+\frac{1}{2})x}{2\sin(\frac{1}{2}x)}$ for $x \neq 0, \pm 2\pi, \pm 4\pi,\dots$

I know that this can be proven inductively. However, I can't get passed the trig. I am pretty sure trig identities can show that the expression above is true for $n=0$, and that if the expression ...
0
votes
3answers
44 views

Prove $4^n > 5*n^2$ where $n\geqslant 3$ is a natural number

I've got this problem out of an exercise booklet and I'm not too familiar with proofs. It looks like I'm supposed to use induction, so far I have: Solving a base case, where $n=3$ So, $4^3 > ...
1
vote
2answers
83 views

Induction proof problem

Prove by induction the following statements: (a) $n! > n^3$ for every $n \ge 6$. (b) prove $\frac{(2n)!}{n!2^n}$ is an integer for every $n\geq 1$ I'm quite terrible with induction so any help ...
2
votes
2answers
2k views

Proving by induction that $ \sum_{k=0}^n{n \choose k} = 2^n$

Prove by induction that for all $n \ge 0$: $${n \choose 0} + {n \choose 1} + ... + {n \choose n} = 2^n.$$ In the inductive step, use Pascal’s identity, which is: $${n+1 \choose k} = {n \choose k-1} ...
0
votes
2answers
94 views

Proof by Math Induction

I have 3 math induction proofs I have been struggling with for a while. I understand how to do summation proofs but these ones, I cant find a general pattern to solve. Please help. 1) $D(n) = {n(n-3) ...
2
votes
5answers
108 views

Given $n \in \mathbb{N}$ prove that a polynomial result gives a natural number.

A friend asked me this question: Prove that for every $n\in \Bbb N$ the next equation result: $\dfrac{n^3}{6}+\dfrac{n^2} {2}+\dfrac{n}{3}$ would be a natural number. My instincts were that i need ...
-1
votes
1answer
107 views

Understanding a proof of the fact that $\binom{n}{k}$ is always a natural number.

Original source of question and solution. Question is on the left, answer is on the right. Question: Notice that all the numbers in Pascal's triangle are natural numbers. Use part (a) to prove by ...
1
vote
1answer
88 views

Inductive step in the induction: $\sum^{n}_{i=0} q^i = \frac {1-q^{n+1}}{1-q}\times2$

I am trying induction for the following formula: $$\sum^{n}_{i=0} q^i = \frac {1-q^{n+1}}{1-q}\times2$$ I have done the initial step which gives me for $n=1$ for both sites $1+q$ In the inductive ...
6
votes
1answer
5k views

What's the difference between simple induction and strong induction?

I just started to learn induction in my first year course. I'm having a difficult time grasping the concept. I believe I understand the basics but could someone explain the summary of simple induction ...
10
votes
2answers
310 views

What's an induction problem that will be hard to answer with “backwards reasoning?”

I'm currently the teaching assistant for a course that serves as an introduction to rigorous proofs, and I've noticed some of my students have a tendency to try and use a sort of "backwards reasoning" ...
3
votes
2answers
73 views

Prove that $ \left(1-\frac{1}{n}\right)^n > \frac{1}{6} $ for $n\geq 2$

Prove that $ \left(1-\frac{1}{n}\right)^n > \frac{1}{6} $ for $n \in \mathbb{N}$, $ n\ge 2$ Indeed, the affirmation is true even if $n$ is not a natural ($ n\geq 2 $ ) and we can prove it using ...
0
votes
2answers
56 views

Prove $\sum_{i=1}^{n}i\left(\begin{array}{c} n\\ i \end{array}\right)=n2^{n-1}$ using induction.

I have already derived the formula $\sum_{i=1}^{n}i\left(\begin{array}{c}n\\i \end{array}\right)=n2^{n-1}$ directly just by doing some algebraic manipulations to the summand, which is indeed proves ...
1
vote
2answers
85 views

How do I prove $2^{n+1} + 2n + 1 = 2^{n+2} - 1$

I am attempting to prove using induction: $\sum_0^n 2i = 2^{n + 1} - 1$ I have gotten to the point where I need to show: $2^{n+1} + 2n + 1 = 2^{n+2} - 1$ How do I prove this? Or should I be ...
1
vote
0answers
43 views

Show by induction… Help

Let $a,n\in\mathbb{N}$, show that there exists $m\in\mathbb{N}$, such that $(a+1)^n=ma+1$ I tried to do by induction on $n$, but found it a bit strange the demonstration. ...
0
votes
4answers
108 views

Need to prove that $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5$ is divisible by $99$ for all $n \in \mathbb{N} $, using induction.

First, obviously, I figured out the base case. So I have $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5 = 99k$ for some $k \in \mathbb{N} $. As for the inductive step, I was thinking about splitting it up ...
3
votes
2answers
110 views

Let $n \in \Bbb N$. Let $p>2$ a prime number. Show that $1^n+2^n+…+(p-1)^n \equiv 0 \pmod {p}$ [duplicate]

This is an exercise in my abstract algebra reader, in the chapter about polynomial rings. Let $n \in \Bbb N$. Let $p>2$ a prime number. And let $n$ not divisble by $p-1$. Show that ...
0
votes
1answer
94 views

Consider a game in which two players take turns removing any positive number of pebbles they want from one of two piles of pebbles.

Consider a game in which two players take turns removing any positive number of pebbles they want from one of two piles of pebbles. The player who removes the last pebble wins the game. Show that if ...
3
votes
3answers
727 views

Use mathematical induction to prove that 9 divides $n^3 + (n + 1)^3 + (n + 2)^3$; Looking for explanation, I already have the solution.

I have the solution for this but I get lost at the end, here's what I have so far. basis $n = 0$; $9 \mid 0^3 + (0 + 1)^3 + (0 + 2)^2 ?$ $9 \mid 1 + 8$ = true Induction: Assume $n^3 + (n + ...
0
votes
1answer
66 views

Proof by induction that $1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$ [duplicate]

How would I go about solving this question? Use induction to prove that for all integers $n ≥ 1$, $$1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$$
2
votes
3answers
531 views

Using induction to prove a result about the Fibonacci sequence

The Fibonacci sequence $F_0, F_1, F_2,...,$ are defined by the rule $$F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$$ Use induction to prove that $F_n\geq2^{0.5n}$ for $n\geq 6$ So far I have done the ...
0
votes
0answers
48 views

How to solve this Discrete math problem [duplicate]

This is a question that was on our previous quiz and I didn't know how to answer it, I would like it if I could get some help explaining how to solve such a question. Thank you in advance. Your ...
0
votes
3answers
88 views

Proof by induction not making sense

Proving by induction. We'd like to show that $2 + 4 + 6 + \cdots+ 2n = n(n + 1)$. A nice way to do this is by induction. Let $S(n)$ be the statement above. An inductive proof would have the following ...
0
votes
1answer
19 views

Induction on a triangular equality related problem

I have to prove $|a_1,a_2,\dots,a_n|\leq |a_1|+|a_2|+\dots+|a_n|$ For $n$ numbers $a_1,a_2,\dots,a_n,\dots$. How can I start this problem? I used this so far (triangular equality set up or rather an ...
0
votes
3answers
278 views

Mathematical induction prove that 9 divides $n^3 + (n+1)^3 + (n+2)^3$ .

How can I use mathematical induction to prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a nonnegative integer?
2
votes
3answers
189 views

Algebra Textbook

Perhaps this questions was asked already, but I browsed through other threads and couldn't find exactly what I am looking for. I am looking for an Algebra Textbook (high-school/undergrad level) that ...
4
votes
3answers
346 views

Proof by induction or contradiction?

I have to prove that $(4k + 3) ^2 - (4k + 3)$ is not divisible by $4$. What would be the best approach for this, proof by induction or contradiction? I've tried both and haven't got very far. Any ...
0
votes
2answers
44 views

Induction with inequality problem

Prove by induction that $2k(k+1) + 1 < 2^{k+1} - 1$ for $ k > 4$. Can some one pls help me with this? I reformulated like this $ 2k(k+1) + 1 < 2^{k+1} - 1 $ $ 2k^2+2k+2<2^{k+1}$ ...
3
votes
1answer
282 views

Use induction to prove that $ 1 + \frac {1}{\sqrt{2}} + \frac {1}{\sqrt{3}} … + \frac {1}{\sqrt{n}} < 2\sqrt{n}$

Use induction to prove that $ 1 + \frac {1}{\sqrt{2}} + \frac {1}{\sqrt{3}} ... + \frac {1}{\sqrt{n}} < 2\sqrt{n} $ My attempt was as follows: Lets assume the inequality is true for n = k $S_k ...
0
votes
2answers
56 views

Given an induction definition, how to calculate elements?

I'm having difficulty with a mathematical problem. I've got the following; The basis is: -1 ∈ V And the induction is; ...
2
votes
2answers
49 views

Proof of expression by induction

Hello I am trying to solve that the following expression is true for all positive integers n: $$(n+1)(n+2)\cdots(2n) = 2^n \cdot 1 \cdot 3 \cdot 5\cdot ... \cdot(2n-1).$$ I know that this question ...
0
votes
3answers
74 views

Mathematical induction proof I'm stuck on

Use mathematical induction to show that $3^{3n} + 2^{n+2}$ is divisible by 5. Any help would be appreciated thanks!
2
votes
0answers
45 views

Induction Problem ($n^2 ≤ 2^n$) [duplicate]

So I have this induction problem: $$n^2 ≤ 2^n \;\text{ for } \; n ≥ 4$$ I know the base case is ($n=4$) which checks out. I know the hyp is ($n=k$) giving $k^2 ≤ 2^k$. However, I am getting ...
0
votes
1answer
56 views

Let f be a positive integer be define recursively by $f(1)=1$ and $f(n+1)=\sqrt{2+f(n)}$ for all integers n. Prove that $f(n) = (2^n)-1$.

Let f: be a positive integer defined recursively by $f(1)=1$ and $f(n+1)=\sqrt{2+f(n)}$ for all integers n. Prove that $f(n)<2$. I am supposed to prove this by using proof of induction. I've ...
1
vote
3answers
64 views

Basic Mathematical Induction [duplicate]

I'm not quite sure how to approach this question. I need to prove that for $$n\ge1$$ $$1^2+2^2+3^3+\dots+n^2=\frac16n(n+1)(2n+1)$$ Do I just plug $1$ and see if $$\frac16(1)((1)+1)(2(1)+1) = ...
2
votes
2answers
93 views

Mathematic induction

Can someone explain to me this : Why we use both, "n" and "n+1" in the third stage if math induction (where we check if statement holds for "n+1". I'll give an example Prove that ...
0
votes
1answer
71 views

What is the first proof that you've done using induction?

Right now in class I'm learning induction and I'm having a hard time to grasp the concepts of it, especially strong induction which confuses me even further. But out of curiosity, what is the first ...
3
votes
2answers
98 views

Mathematical Induction that seems v difficult

i have a problem with a mathematical induction but i find it really hard to solve: Q: $\sum_1^n iax^i = \frac{ax(1-x^{n}-nx^{n}+nx^{n+1})}{(1-x)^{2}}$ n is all positive integer I know it can be ...
3
votes
4answers
152 views

Hint to prove that $\phi^n + \phi'^n$ is an integer.

I was solving some induction exercises but I found this that I could not solve. Let $n \in \mathbb{N}$, prove that $\phi^n + \phi'^n$ is an integer where $\phi=\frac{1+\sqrt{5}}{2}$ and ...
2
votes
1answer
68 views

Why are strict inequalities stronger than non-strict inequalities?

I'm working with induction proofs involving inequalities and I am encountering example proofs that wish to show things of the sort, $n!\le\ n^n$ for every positive integer. The proof given in the ...
1
vote
3answers
262 views

Mathematical induction - what makes it true?

I am trying to work through an example in my book and it just seems nonsensical Why is mathematical induction a valid proof technique? The reason comes from the well ordering property, listed in ...
1
vote
3answers
84 views

How to do this Math induction problem?

Show that: $$\frac n3 + \frac n9 + \frac {n}{27} + \cdots = \frac n2.$$ When I start with $\frac 13 + \frac 19 + \frac {1}{27}$ it leads to a number close to $.5$ but it's not exactly $.5$.
1
vote
2answers
47 views

An induction problem.

I am trying to prove the following problem by induction on $n$. Let $T: (0,1]\rightarrow (0,1]$ be given by $T(x)=\left\{ \begin{array}{ll} 2x & \quad \text{if} \hspace{4mm} ...
1
vote
2answers
260 views

Can mathematical induction be used to disprove something?

I saw this to be the rule of inference for mathematical induction : Now consider : as L.H.S. and as R.H.S.. Now if suppose, while trying to prove P(k) -> P(k+1), in the left hand side of ...
0
votes
4answers
104 views

Proof that $\left(\sum^n_{k=1}x_k\right)\left(\sum^n_{k=1}y_k\right)\geq n^2$

If $x_1,...,x_n$ are positive real numbers and if $y_k=1/x_k$, prove that $$\left(\sum^n_{k=1}x_k\right)\left(\sum^n_{k=1}y_k\right)\geq n^2.$$ I've been learning induction, and I've come across ...
0
votes
1answer
65 views

Inequality with a sum and factorial

For a homework assignment we have the following question that I'm stuck on. Let $ 0 \leq y \leq 1 $ be given. $\forall m \in \mathbb{N}$, define $ \displaystyle S_m(y)=\sum_{k=0}^m \binom{m}{k}y^k$. ...
3
votes
2answers
84 views

Prove through induction that $3^n > n^3$ for $n \geq 4$

I'm new to induction and have not done induction with inequalities before, so I get stuck at proving after the 3rd step. The question is: Use induction to show that $3^n > n^3$ for $n \geq ...
0
votes
2answers
50 views

Induction on the length of a $\lambda$-term

I'm a bit confused about a statement that I see often in the $\lambda$-calculus literature. Namely, what exactly does the following statement mean: "By induction on the length of $M\in\Lambda$." ? In ...